Google Code Jam 2020 Qualification Round - ESAb ATAd

問題: ESAb ATAd - Code Jam

問題概要

'0' と'1' のみからなる長さ$B$ の文字列が与えられる (制約は本節最後を参照)。この文字列に対して，次のクエリを 150 回まで投げることができる。

文字列の $i$ 文字目は '0' と'1' のどちら？

1回目，11回目，21回目……のクエリが投げられたとき，サーバがクエリの回答を渡す前に，文字列に以下の操作のうちいずれか1つが行われる。

何もしない
complement : '0' を '1' に，'1' を'0' にする
reverse : 文字列を逆順にする
compliment と reverse の両方を適用する

適用された動作が何かは一切わからない。

このとき，長さ $B$ の文字列は現在どうなっているかを答えよ。文字列の初期状態を答える必要はなく，現時点での状態を $B$ 文字分揃って答えられれば良い。

制約

テストケース数 : $T \leq 100$

Test Set 1 : $B = 10$

Test Set 2 : $B = 20$

Test Set 3 : $B = 100$

解法概要

中心からの距離が同じ文字列 (例えば $B = 100$ なら 1 番目と 100 番目，2 番目と 99 番目，……) をペアで見ていく。$i$ 番目の文字と $j$ 番目の文字のペアを今後 $(i, j)$ のように表すとする。

10回目のクエリまでは文字列に変更はないので，文字列の外側から見ていって $(i+1, B-i) (0 \leq i \lt 5)$ の5ペアを確定させていく。

11回目以降は10回ごとに文字列に変更が入る可能性があるので，それを検知する必要がある。文字列の変更は，今まで見たペアの中で同じ数字だったペアと違う数字だったペアをあらかじめ覚えておいて，その数字が今どうなっているかを聞き直すことで検知する。この検知には 2 回分のクエリを消費するので，11回目以降は「文字列の状態の検知のためのクエリ2回→今まで不明だった部分を聞くクエリ8回」という 10 クエリ 1 セットの繰り返して，文字列に反映された操作を常に把握して文字列全体を作っていく。

例えば，外側から見ていったときに最初に見つけた同じ数字のペアの値が，前回見たときは両方 0 だったのに今は 1 に変更されているとしよう。これは文字列が complement されたことを意味する。文字列の中心からの距離が同じペアであれば，reverse されていようといまいと complement されれば必ず元の数字とは別の数字に変更されるからである。なお，reverse されたかどうかはこの段階では分からない。

reverse されているかどうかは，外側から見ていったときに最初に見つけた違う数字のペアを使う。違う数字のペアは，complement または reverse されると前回の値からは変更になる。ただし，complement と reverse の両方が適用されると前回の値と同じになる。したがって，違う数字のペアの値が変更になっているとき，complement されているなら reverse はされておらず，complement されていないなら reverse されている。変更になっていない場合は，complement されているなら reverse されていて，complement されていないなら reverse もされていない。要するに，「変更になったか？」と「complement されているか？」の排他的論理和として書ける。

同じ数字のペア / 違う数字のペア，片方しか見つかっていない場合には，それぞれ complement / reverse だけを考慮すればよい。reverse / complement されても，その時点で判明している部分の文字列はまったく変わらないためである。ただしこの場合，10 クエリ 1 セットのクエリ回数を壊さないために，適当にダミーのクエリを投げておく必要がある。11回目以降，不明部分を外側から埋めていく途中で同じ数字のペア / 違う数字のペアを新しく見つけたらそれを記録しておくのを忘れないこと。

ソースコード

#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;

int B, same_pair_i = -1, diff_pair_i = -1, same_pair_num, diff_pair_num;
int a[100];

// i+1 番目と B-i 番目を読み込む
void read_pair(int i) {
    int r1, r2;
    cout << i+1 << endl;
    cin >> r1;
    a[i] = r1;
    cout << B-i << endl;
    cin >> r2;
    a[B-1-i] = r2;
    if(r1 == r2) {
        if(same_pair_i == -1) {
            same_pair_i = i;
            same_pair_num = r1;
        }
    } else {
        if(diff_pair_i == -1) {
            diff_pair_i = i;
            diff_pair_num = r1;
        }
    }
}

bool solve() {
    same_pair_i = -1;
    diff_pair_i = -1;
    for(int i=0;i<5;++i) {
        read_pair(i);
    }

    for(int i=5;i<B/2;i+=4) {
        int r;
        bool is_complemented = false;
        if(same_pair_i != -1) {
            cout << same_pair_i+1 << endl;
            cin >> r;
            is_complemented = (r != same_pair_num);
            same_pair_num = r;
        } else {
            cout << 1 << endl;
            cin >> r;
        }
        bool is_reversed = false;
        if(diff_pair_i != -1) {
            cout << diff_pair_i+1 << endl;
            cin >> r;
            is_reversed = (r != diff_pair_num) ^ is_complemented;
            diff_pair_num = r;
        } else {
            cout << 1 << endl;
            cin >> r;
        }
        for(int ii=0;ii<i;++ii) {
            if(is_complemented) {
                a[ii] = 1 - a[ii];
                a[B-1-ii] = 1 - a[B-1-ii];
            }
            if(is_reversed) {
                swap(a[ii], a[B-1-ii]);
            }
        }

        for(int j=0;j<4&&i+j<B/2;++j) {
            read_pair(i+j);
        }
    }

    for(int i=0;i<B;++i) {
        cout << a[i];
    }
    cout << endl;
    char c;
    cin >> c;
    return c == 'Y';
}

int main() {
    int T;
    cin >> T >> B;
    while(T-- && solve());
}

所感

太字部分は私が誤読していた部分です。