Google Code Jam 2019 Qualification Round : Dat Bae

問題. Dat Bae

台のマシンがあり， から までの番号付がなされている．それらのマシンの内 台が壊れている．次で定義するマスタとの間のインタラクティブな通信を高々 回行いどのマシンが壊れているかを特定せよ．
インタラクティブな通信とは，長さ の 0 と 1 からなるビット列 をマスターへ送ると，マスターから 台の各マシンに1ビットが送信される． 番目のマシンはマスターから を受信する．壊れていないマシンは受信したビットをマスターへ送信して，壊れているマシンは何も送信しない．マスターは各コンピュータから受信した1ビットをマシンの番号の昇順に並べて，その長さ のビット列を送り返す．

制約： ，　，　

解法

マスタに送信する1回目のビット列 を構成する． を左から順番にブロックサイズが となるように分割する．各ブロック内のビットが同じになるように，左のブロックから順番に 1 と 0 を繰返し割り当てる． をマスタへ送信して， を受信する． を見るとどのブロックにいくつ壊れていないマシンが存在するかが分かるので，後は各ブロック内を同様に長さ と分割してマスタにビット列を送信することによって区間内の壊れていないマシン数が分かる．
初めから と分割する方法だと通信回数が となり制約を満たさない．ここで， の数が小さいことに着目して初めは長さ のブロックに分割すると， のサイズは高々 なので 回の通信で答えを求めることができる．

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using Section = tuple<int, int, int>;
using Sections = vector<Section>;

void PrintAnswer(vector<int> &broken) {
    const int n = broken.size();
    sort(broken.begin(), broken.end());
    for (int i = 0; i < n; ++i) {
        cout << broken[i];
        if (i != n - 1) cout << ' ';
    }
    cout << endl;

    int verdict;
    cin >> verdict;
    if (verdict == -1) exit(0);
}

inline void change(char &c) { c = (c == '0' ? '1' : '0'); }

void Solve() {
    int N, B, F, S;
    cin >> N >> B >> F;
    S = N - B;

    Sections secs;
    vector<int> broken;

    // ブロックサイズ B で分割
    string op, res;
    char parity = '1';
    for (int i = 0; i < N; i += B) {
        op += string(min(N - i, B), parity);
        change(parity);
    }

    cout << op << endl;
    cin >> res;
    parity = '1';
    for (int i = 0, idx = 0; i < N; i += B) {
        if (idx == S || res[idx] != parity) {
            int num = 0;
            for (int j = i; j < min(N, i + B); ++j) {
                ++num;
                broken.push_back(j);
            }
            secs.emplace_back(Section(i, min(N, i + B), 0));
        }
        else {
            int num = 0;
            while (idx < S && res[idx] == parity && num < B) { ++num; ++idx; }
            secs.emplace_back(Section(i, min(N, i + B), num));
        }
        change(parity);
    }

    if ((int)broken.size() == B) {
        PrintAnswer(broken);
        return ;
    }

    // 領域を二分探索的に分割する
    while ((int)broken.size() < B) {
        op.clear();
        parity = '1';

        for (const auto &s : secs) {
            const int len = get<1>(s) - get<0>(s);
            const int num = get<2>(s);
            if (num == 0 || num == len) { // 分割しない
                op += string(len, parity);
                change(parity);
            }
            else {
                const int mid = (get<0>(s) + get<1>(s)) / 2;
                op += string(mid - get<0>(s), parity);
                change(parity);
                op += string(get<1>(s) - mid, parity);
                change(parity);
            }
        }
        cout << op << endl;
        cin >> res;
        if (res == "-1") exit(0);

        Sections nxt_secs;
        parity = '1';
        for (size_t i = 0, idx = 0; i < secs.size(); ++i) {
            const int len = get<1>(secs[i]) - get<0>(secs[i]);
            const int num = get<2>(secs[i]);
            if (num == 0 || num == len) { // 分割されていない
                nxt_secs.emplace_back(secs[i]);
                idx += num;
                change(parity);
            }
            else {
                const int mid = (get<0>(secs[i]) + get<1>(secs[i])) / 2;
                int num_one = 0, num_zero = 0;
                for (int j = 0; j < num; ++j) {
                    if (res[idx + j] == '0') ++num_zero;
                    else ++num_one;
                }
                idx += num;
                Section s1(get<0>(secs[i]), mid, num_zero);
                Section s2(mid, get<1>(secs[i]), num_one);
                if (parity == '1') {
                    get<2>(s1) = num_one;
                    get<2>(s2) = num_zero;
                }
                change(parity);
                change(parity);
                nxt_secs.emplace_back(s1);
                nxt_secs.emplace_back(s2);

                if (get<2>(s1) == 0) { // 区間 s1 のマシンはすべて壊れている
                    for (int j = get<0>(s1); j < get<1>(s1); ++j) {
                        broken.push_back(j);
                    }
                }
                if (get<2>(s2) == 0) { // 区間 s2 のマシンはすべて壊れている
                    for (int j = get<0>(s2); j < get<1>(s2); ++j) {
                        broken.push_back(j);
                    }
                }
            }
        }
        secs = move(nxt_secs);
    }

    PrintAnswer(broken);
}

int main() {
    int T;
    cin >> T;
    while (T--) Solve();

    return 0;
}

　

ローカルでのテスト方法

ローカル環境でのテストのために testing_tool.py というPython言語で書かれたプログラムが与えられる．作成したプログラムの実行ファイルを my_solution として次を実行するとテストが行える．
testing_tool.py は引数を１つ取り今回は 0 とする．mkfifo コマンドで名前付きパイプ FIFO を作成する．そして，python3 testing_tool.py 0 への標準入力を FIFO から，標準出力をパイプ | を用いて実行ファイル ./my_solution への標準入力へとリンクしている．また，./my_solution の標準出力を FIFO へリンクしている．このようにすることでプロセス間通信が行えて，インタラクティブ問題のテストが行える．

$ mkfifo FIFO  # 名前付きパイプを作成
$ python3 testing_tool.py 0  < FIFO | ./my_solution > FIFO  # テストを実行

　
他の方法として，nico_shindanninさんのツイートが参考になる．

GCJインタラクティブ問題でどハマリしたので、まとめ。
● テスターツールは2つある。１つはGCJ共通用・１つは問題別。
● python interactive_runner.py python testing_tool.py 1 -- ./a.out のように使う。
● デバッグ出力はcerrのようにエラー出力で。

— nico_shindannin (@nico_shindannin) 2019年4月7日

インタラクティブ問題を初めて解いたのでデバッグが大変だった．
GCJ は実装が大変（他の問題は多倍長整数が要求されたりと）．
Tシャツもらいたいな．