BOJ 24979 - COW Operations

BOJ 24979 - COW Operations

항상 어떤 두 문자가 있으면 다른 문자 한개로 바꿀 수 있음을 관찰한다.

$OW \to C$ 같은 식이다. 물론 $WO \to 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는 하나도 없게 되어야 한다.