Google Code Jam 2019 Round1B : Draupnir

問題. Draupnir

$X$ -day ring と呼ばれる指輪がある．1つの $X$ -day ring は出現した日から $X$ 日ごとに $X$ -dary ring を1つ複製するということを永遠に続ける．0 日目に各 $X$ -day ring が $R_X$ 個出現する（ $R_X$ は未公開）．
「 $i \,\,(1 \le i \le D)$ 日目にある指輪の総数の $2^{63}$ による剰余はいくつか」という質問を高々 $W$ 回行い，すべての $R_X$ を求めよ．

制約： $1 \le X \le 6$ ，　 $1 \le D \le 500$ ，　 $0 \le R_X \le 100$ （ただし，少なくとも1つの $R_X$ は正）
　　　 $W = 2, 6$

解法

$i$ 日目に対するクエリの戻り値を $n_i$ とする． $n_i$ は62ビットの非負整数であり問題から，
　　 $n_i \equiv 2^i R_1 + 2^{\lfloor \frac{i}{2} \rfloor} R_2 + 2^{\lfloor \frac{i}{3} \rfloor} R_3 + 2^{\lfloor \frac{i}{4} \rfloor} R_4 + 2^{\lfloor \frac{i}{5} \rfloor} R_5 + 2^{\lfloor \frac{i}{6} \rfloor} R_6 \bmod 2^{63}$
となる．2回のクエリ $n_{185}$ と $n_{55}$ ですべての $R_X$ を求める．

解法の前に使用するビット演算について説明する． $R_X$ は100以下の非負整数なので7ビットで表現可能である．ここで，整数 $n$ の二進表記を $n_{(2)}$ とすると， $2^k \times n$ は $n_{(2)}$ を $k$ ビットだけ左シフトしたもので， $n / 2^k$ は $k$ ビットだけ右シフトしたものである．ただし，最上位ビットは0埋めを行う．

$n_{185}$ に対するクエリの戻り値は，
　　 $n_{185} \equiv 2^{185} R_1 + 2^{92} R_2 + 2^{61} R_3 + 2^{46} R_4 + 2^{37} R_5 + 2^{30} R_6 \bmod 2^{63}$
となる．ここから， $R_6, R_5, R_4$ の値が次のように分かる．
　・ $R_6$ は $n_{185}$ の $30$ から $36$ ビット目の値に等しい（ $k = 30$ ）
　・ $R_5$ は $n_{185}$ の $37$ から $43$ ビット目の値に等しい（ $k = 37$ ）
　・ $R_4$ は $n_{185}$ の $46$ から $52$ ビット目の値に等しい（ $k = 46$ ）
これらの値のビット列は互いに交差しないので $n_{185}$ を $k$ ビット右シフトして $2^7$ で剰余をとると求まる． $R_1, R_2, R_3$ は戻り値のビット数で表現できないので求めることができない（ $R_3$ は下位2ビットだけ分かる）．

$n_{55}$ に対するクエリの戻り値は，
　　 $n_{55} \equiv 2^{55} R_1 + 2^{27} R_2 + 2^{18} R_3 + 2^{13} R_4 + 2^{11} R_5 + 2^{9} R_6 \bmod 2^{63}$
となる．ここから， $R_1, R_2$ の値が次のように分かる．
　・ $R_1$ は $n_{55}$ の $55$ から $61$ ビット目の値に等しい（ $k = 55$ ）
　・ $R_2$ は $n_{55}$ の $27$ から $33$ ビット目の値に等しい（ $k = 27$ ）
これらの値のビット列は互いに交差しないので $n_{55}$ を $k$ ビット右シフトして $2^7$ で剰余をとると求まる．ここで， $R_3$ は $n_{55}$ の $18$ から $24$ ビット目の値にはならない．なぜならば， $R_4$ が $n_{55}$ の $13$ から $19$ ビット目の範囲となり， $R_3$ の領域と交差するからである．ただし，ここまでで $R_3$ 以外のすべての値が求まっているので，
　　 $R_3 = \frac{n_{55} - (2^{55} R_1 + 2^{27} R_2 + 2^{13} R_4 + 2^{11} R_5 + 2^{9} R_6)}{2^{18}}$
として求めることができる．

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ull = unsigned long long;

void Solve(const int W, int verdict = 1) {
    const int DAYS = 6;
    const ull MOD = 1 << 7;
    vector<ull> r(DAYS);

    ull n185;
    cout << "185" << endl;
    cin >> n185;
    r[3] = (n185 >> 46) % MOD;
    r[4] = (n185 >> 37) % MOD;
    r[5] = (n185 >> 30) % MOD;

    ull n55;
    cout << "55" << endl;
    cin >> n55;
    r[0] = (n55 >> 55) % MOD;
    r[1] = (n55 >> 27) % MOD;
    r[2] = (n55 - ((r[0] << 55) + (r[1] << 27) + (r[3] << 13)
                   + (r[4] << 11) + (r[5] << 9))) >> 18;

    for (int i = 0; i < DAYS; ++i) {
        cout << r[i];
        if (i != DAYS - 1) cout << " ";
    }
    cout << endl;

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

int main() {
    int T, W;
    cin >> T >> W;
    for (int i_case = 1; i_case <= T; ++i_case) {
        Solve(W);
    }

    return 0;
}

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

$R_3$ が求まらな〜いと悩みすぎた． $n_{55}, n_{185}$ は実験で $R_i$ と $R_{i + 1}$ の $7 \le \lfloor \frac{n}{i} \rfloor - \lfloor \frac{n}{i + 1} \rfloor$ となるものを見つけて求めた．この問題を爆速で解く人たちは凄いな．