Google Code Jam 2019 Round1A : Golf Gophers

問題. Golf Gophers

18ホールあるゴルフ場の各ホールにちょうど1つの風車がある．毎晩， $i$ 番ホール（ $1 \le i \le 18$ ）にある風車のブレード数を任意に $2 \le B_i \le 18$ に決めて， 0 番目のブレードが真下にあるように設定する．ただし，ブレードは時計回りに $0, 1, \ldots, B_{i} - 1$ と番号付けされている．
各風車のブレード数を設定した後に， $G$ 人のゴルファーがそれぞれ1つの風車を独立かつ一様ランダムに選択して，半時計回りに1ブレード分だけ回転する（真下にあるブレード番号が $j$ のとき，回転後に真下にあるブレード番号は $j + 1 \bmod B_i$ ）．翌日の朝に各風車の真下にあるブレード番号が確認できる．
整数 $N, M$ が与えられる．上で説明した18ホールの各風車のブレード数を決めるクエリを高々 $N$ 回行い，レスポンスの翌日の各風車の真下にあるブレード番号をもとにゴルファーの人数 $G$ を求めよ．ただし， $G$ は1以上 $M$ 以下の整数である．

制約1： $N = 365, M = 100$
制約2： $N = 7, M = 10^6$

解法．中国剰余定理

中国剰余定理（中国剰余定理と法が互いに素でない場合への拡張 | 高校数学の美しい物語）をもとにクエリを構成する．中国剰余定理（Chinese remainder theorem）とは，互いに素な整数 $n_1, n_2, \ldots, n_k$ に対して， $k$ 本の連立合同式 $x \equiv a_i \bmod n_i$ 　( $i \in \{1, 2, \ldots, k\}$ ) を満たす整数 $x$ が 0 以上 $n_1 n_2 \cdots n_k$ 未満の範囲に唯一に存在することを述べた定理である．

$i$ 番目のクエリで行う各風車のブレード数をすべて同じ整数 $p_i$ とする．このクエリに対して，翌日の各風車の真下にあるブレード番号の総和を $s_i$ とすると，
　　 $s_i \equiv G \bmod p_i$
が成り立つ．したがって上手く $p_i$ を設定すれば中国剰余定理から 0 以上 $p_1 p_2 \cdots p_N$ 未満の整数を一意に求めることができる．ここで， $(p_1, p_2, \ldots, p_7) = (5, 7, 9, 11, 13, 16, 17)$ とする．各異なる $p_i, p_j$ は互いに素で， $p_1 p_2 \cdots p_7 = 12,252,240 \ge 10^6$ なので，入力の制約を満たすどんな $G$ に対しても高々 7 回のクエリで答えを求めることができる．

計算時間： $O(M)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

void Solve(const int N, const int M) {
    constexpr int NUM_QUERY = 7;
    const array<int, NUM_QUERY> query_p = {5, 7, 9, 11, 13, 16, 17};
    array<int, NUM_QUERY> response;

    constexpr int NUM_WINDMILL = 18;
    for (int i = 0; i < NUM_QUERY; ++i) {
        for (int j = 0; j < NUM_WINDMILL; ++j)
            cout << query_p[i] << (j == NUM_WINDMILL - 1 ? "" : " ");
        cout << endl;

        int sum_response = 0;
        for (int j = 0, res_j; j < NUM_WINDMILL; ++j) {
            cin >> res_j;
            sum_response += res_j;
        }

        response[i] = sum_response % query_p[i];
    }

    for (int g = 1; g <= M; ++g) {
        bool all_match = true;
        for (int i = 0; i < NUM_QUERY; ++i) {
            if ((g % query_p[i]) != response[i]) {
                all_match = false;
                break;
            }
        }

        if (all_match) {
            cout << g << endl;

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


int main() {
    int T, N, M;
    cin >> T >> N >> M;

    while (T--) Solve(N, M);

    return 0;
}

インタラクティブ問題のローカルでのテスト方法は次を参考．
Google Code Jam 2019 Qualification Round : Dat Bae - 忘れても大丈夫

ブレード数を一定にすればどうにかできるのではと考えたけど上手く構成できなかったのでkmjpさんのブログを参考にした．
　Google Code Jam 2019 Round 1A: B. Golf Gophers - kmjp's blog
中国剰余定理を知った時は目から鱗だったけど，これ知らなかったとき思いつく自信がまったくない．