GCJ2019 Round1B Draupnir - ちゃっくのメモ帳

GCJのインタラクティブ問題に対するメモ

ツールはコンテストページからinteractive_runner.pyとtesting_tool.pyを使用する。
使い方は次のコマンドを...(実行ファイルをa.outとする)

python3 interactive_runner.py python3 testing_tool.py <コマンドライン引数> -- ./a.out

また、各出力の後にはフラッシュする必要があるから注意(c++ならcout << flush;をいれるとか...)

注意
この問題だけの性質なのか知らないが、問題の最初に問題の個数Tが与えられる。
そして各問題の後に「その問題に正解したかどうか?」が1(正解),-1(不正解)で与えられるのでこれを処理する必要がある。
これを正しく処理しないとTLEになりがち。

問題概要

インタラクティブ問題。
0日目にRing1~6までそれぞれR1,...,R6個ある。(各Riに対してRi<=100)
Ring1は1日毎,Ring2は2日毎,...,Ring6は6日毎に2つに分裂する。
初期値wが与えられ、次の質問をw回行うことができる。
「d日目のRingの合計はいくつか?」
(ただし、質問の答えは2^63で与えられる)
w回の質問で、それぞれのRingの初期値R1,...,R6を求めよ。
ただし、smallはw=6,largeはw=2となっている

解説

d日目の $Ring_i$ の数は次のように表される。 $2^{\lfloor \frac{d}{i} \rfloor}R_i$ 個。
つまりd日目の合計数は次のようになる。
$2^d R_1 + 2^{d/2} R_2 + 2^{d/3} R_3 + 2^{d/4} R_4 + 2^{d/5} R_5 + 2^{d/6} R_6$
ここで、十分に大きいdに対して $2^d R$ は $2^63$ でmodを取ると0になる。
そこで前3つと後ろ3つに切り分けることを考える。
つまり、 $d,d/2,d/3$ は $2^{63}$ を超え、 $d/4$ は $2^{63}$ を超えないようにdを設定する。例えばd=189とする。
この時、
$2^{189} R_1 + 2^{94} R_2 + 2^{63} R_3 + 2^{47} R_4 + 2^{37} R_5 + 2^{31} R_6$
これは $mod 2^{63}$ で計算すると次の式と等価になる。
$2^{47} R_4 + 2^{37} R_5 + 2^{31} R_6$
これで後ろ3つのR4~R6だけを切り出すことができる。Rの上限は100なのでR4,R5を探索しR6を決定すればよい。
ただし、ここで注意が必要で、R4,R5,R6は複数通り計算できる場合がある。
例えば R5,R6だけを考えると $2^{37} R_5 + 2^{31} R_6$ は
$R_5 = 1, R_6=1$ のときと $R_5=0,R_6=1+2^{6}$ で同じ値になる。
ここで重複が起きないようにdを設定することができる。
上の計算式において $2^{6}$ はR5とR6の係数の差が出ているのでこの係数が十分に大きくなれば $R_i \leq 100$ の制限から重複が起きなくなる。
例えばd=210にすると係数の差が100以上になるので重複がなくなる。

この時点で後ろ3つの値が確定しているのでもう1つのクエリで前3つの値を求めれば良い。
これは後ろ3つの値を求めるときと同様であるので省略。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
using ll = long long;


int t,w;
void solve(){
    ll in210,in42;
    cout << 210 << endl;
    cout << flush;
    cin >> in210;
    cout << 42 << endl;
    cout << flush;
    cin >> in42;
    vector<ll> k210(7),k42(7);
    vector<ll> x(7);
    rep(i,w-2){
        cout << 1 << endl;
        cout << flush;
        ll tmp; cin >> tmp;
    }


    for(int i=1;i<=6;i++) k210[i] = (1ll<<(210/i));
    for(int i=1;i<=6;i++) k42[i] = (1ll<<(42/i));

    for(x[4]=0;x[4]<=100;x[4]++){
        for(x[5]=0;x[5]<=100;x[5]++){
            x[6] = (in210 - k210[4]*x[4] - k210[5]*x[5]) / k210[6];
            if(x[6]<0 or x[6]>100) continue;
            for(x[1]=0;x[1]<=100;x[1]++){
                for(x[2]=0;x[2]<=100;x[2]++){
                    ll sum = 0;
                    for(int i=1;i<=6;i++) if(i!=3){
                        sum += k42[i] * x[i];
                    }
                    x[3] = (in42-sum) / k42[3];
                    if(x[3] < 0 or x[3] > 100) continue;

                    for(int i=1;i<=6;i++) cout << x[i] << " ";
                    cout << endl;
                    cout << flush;
                    return;
                }
            }
        }
    }
}

int main(){
    cin >> t >> w;
    rep(i,t){
        solve();
        ll st; cin >> st;
        if(st==-1){
            cerr << "Error at " << i << endl;
            return 0;
        }
        cout << flush;
    }
    return 0;
}

感想

コンテスト中はインタラクティブツールの使い方がわからず終わってしまった....
問題自体はそんなに難しくないのでこれくらいならLargeまで解きたかった。