BOJ 24979 - COW Operations
항상 어떤 두 문자가 있으면 다른 문자 한개로 바꿀 수 있음을 관찰한다.
OW→C 같은 식이다. 물론 WO→C도 가능하다.
그리고 문자를 어떤 순서대로 합쳐도 항상 마지막에 나오는 문자는 동일하다. (마지막에 나오는 문자가 빈 문자일 수도 있다.)
따라서 l,r 에 대해 나는 sparse table로 풀었는데 관찰을 더하면 그냥 prefix sum으로 풀 수 있다.
string conv(char a, char b) {
if (a == 'x') return string(1, b);
if (b == 'x') return string(1, a);
if (a == b) return "x";
for (char c: "COW") {
if (c != a && c != b) return string(1, c);
}
assert(0);
}
const int LOG = 20;
char table[LOG][200005];
void solve() {
string s;
cin >> s;
int Q;
cin >> Q;
for (int i = 0; i < sz(s); i++) table[0][i] = s[i];
for (int k = 1; k < LOG; k++) {
for (int i = 0; i + (1 << k) - 1 < sz(s); i++) {
table[k][i] = conv(table[k - 1][i], table[k - 1][i + (1 << (k - 1))])[0];
}
}
while (Q--) {
int l, r;
cin >> l >> r, l--, r--;
int d = r - l + 1;
char c = 'x';
int ss = l;
for (int k = LOG - 1; k >= 0; k--) {
if (d & (1 << k)) {
c = conv(c, table[k][ss])[0];
ss += (1 << k);
}
}
if (c == 'C') cout << 'Y';
else cout << 'N';
}
}
에디토리얼
C,O,W 를 범위에 존재하는 c,o,w 개수라고 하자.
prefix sum으로 전처리하면 된다.
어떠한 연산도 C,O,W 중 두 개의 합의 parity를 변하지 못하게 함을 관찰한다.
쿼리는 명백히 O+W 가 홀수일 때 NO이다.
왜냐면 O, W 를 모두 지워 0(짝수)개를 만들어야 하는데 홀수개라면 불가능하기 때문이다.
마찬가지인 이유로 C+O나 C+W가 짝수라면 불가능하다. 결국 마지막에 C 가 하나남으려면 이것의 parity는 홀수여야 하기 때문이다.
남은것은 O+W 가 짝수며 C+O 가 홀수일 때 항상 정답이 YES라는 것이 필요충분조건이라는 것을 증명하는 것이다.
일단 모든 W를 제거해보고 몇번의 과정을 거쳐 동일한 것을 모두 지운다.
그럼 C와 O의 alternating string이 나온다.
우린 OCO -> C 가 가능하기 때문에 O가 최대 하나 남을 때 까지 이 과정을 반복한다.
O+W 가 짝수였다면 O는 하나도 없게 되어야 한다.
Comments