BOJ 28265 - Colored-Dealt

BOJ 28265 - Colored-Dealt

차분공격이라는 이상한 태그인데, 푸는법은 단순하다.

처음에 $R$을 $N$개 넣으면 일단 반대쪽의 총 합이 나온다.

이제 $BBBBBR,~ BBBBRR, ~ BBBRRR$ 처럼 넣어보는 것이다.

그럼 $N-1$ 번 쿼리를 날려 반대쪽 $N-1$ 번의 숫자를 알 수 있고 처음에 알아낸 반대쪽의 총 합을 거기서 빼면 나머지 하나도 알아낼수 있다.

왜냐면 $BBBBBR$ 을 넣는다고 하면, 무조건 $BBBBB$ 에 상대방의 마지막 한 문자의 곳의 값이 나올 수 밖에 없기 때문이다.

이미 젤 오른쪽에 $R$이 들어가있기 때문에 상대방의 반대쪽 처음 글자가 $R$ 이여도 그 값이 나올 것이고, $G,B$ 라면 당연히 그 값이 나올 것이다.

처음부터 $BBBBBR$ 을 넣고 $RRRRRR$ 까지 $N$ 번 쿼리를 날려도 된다.

string guess(int N) {
   string ret(N, '?');
   int t = design(string(N, 'R'));
   int initial = t;

   if (N == 1) {
      if (initial == 1) return "R";
      if (initial == 2) return "G";
      if (initial == 3) return "B";
   }

   string qry = string(N, 'B');
   qry[N - 1] = 'R';
   int c = design(qry);

   ret[0] = "RGB"[c - 1 - 3 * (N - 1)];

   // ret1을 구한다고 하자. 0~N-3 까지 모두 B로 하고, N-2~N-1은 R로 한다.

   int qsum = ret[0] == 'R' ? 1 : ret[0] == 'G' ? 2 : 3;
   qsum += (N - 1) * 3;
   for (int i = 1; i < N - 1; i++) {
      qsum -= 3;

      qry[N - 1 - i] = 'R';
      c = design(qry);

      if (c - qsum == 1) ret[i] = 'R';
      if (c - qsum == 2) ret[i] = 'G';
      if (c - qsum == 3) ret[i] = 'B';

      qsum += ret[i] == 'R' ? 1 : ret[i] == 'G' ? 2 : 3;
   }

   int tmp = 0;
   for (int i = 0; i < N - 1; i++) {
      if (ret[i] == 'R') tmp++;
      else if (ret[i] == 'G') tmp += 2;
      else tmp += 3;
   }
   if (initial - tmp == 3) ret[N - 1] = 'B';
   else if (initial - tmp == 2) ret[N - 1] = 'G';
   else ret[N - 1] = 'R';
   reverse(all(ret));
   return ret;
}