naoya_t@hatenablog

いわゆるチラシノウラであります

Google Code Jam 2019 Round 2

5/18(土) 23:00-25:30

B(interactive問題)の1完のみ23点で1231位。R3進出(&TシャツGET)ならず。
R1のinteractiveも3問とも(R1A,R1B,R1C)解いたけど、今年のinteractiveはすごく自分向きだった。

(あとで書く)

New Elements: Part 1

(あとで書く)
→WA(n)

終了後

doubleで計算したのが敗因?と思って有理数にしてみたけどWA
どこがバグってるんだろう
あとで調べる

Pottery Lottery

とりあえず最初に思いつくやつ

  • 1つを除いた他の瓶に満遍なく偽IDを放り込んでいく
  • 温存していた瓶に最後に100を入れる

これでは全然勝てない(3割も取れない)

(当然のことながら)結構偏るものなので
途中まで適当に推移させて、一度中身を数えた上でその後の方針を決めたほうがよさそう。
(どのくらいの日数を前半の適当推移フェーズにあてるのが良いかは実験して決めよう)

適当推移期間の偽IDの投入方法は、ランダム(なり番号順なり)にするだけではいまいちで、
投入しない瓶が幾つかあったほうが偏りを生み出せてよさそう。

中身のチェックには20回かかる。
同時にはできないので誤差が生じる。これはその後の得票数の期待値で補正するしかない。

チェック+期待値補正した中で一番少ないやつを1つキープして、それ以外の瓶に少ない方から(これはpriority_queueを使って、少ないうちは何度も)偽IDを放り込んでいくことで、一番少ないやつとの差を2以上にしておきたい。

そして最終日に、満を持してID100を投票する。

100回のオペレーションの使い方(最終案)
  • 55(前寄り16個に適当に入れるフェーズ)
  • 20(調査フェーズ。答えを0.05*残り回数で補正)
  • 24(最小以外に入れるフェーズ)
  • 1(最小に100を入れるフェーズ)

で、ローカルテスト(testing_tool.py)で Got 238/250 (95.2%) が出た。
55と16は適当に色々試してみて一番良かったやつ。

testing_tool.pyの結果を信じてsubmitして一発AC
→AC

// マクロ略
void say(int v, int p){
    printf("%d %d\n", v, p);
    fflush(stdout);
}

vector<int> ask(int v){
    say(v,0);

    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    return a;
}

int today(){
    int curr_day; cin >> curr_day;
    return curr_day;
}

void testcase(int case_id) {
    int pre=55, post=80-pre;
    int w = 4;

    rep(i,pre) {
        int t = today();
        say(1+ i%(20-w), t);
    }

    vector<vector<int>> asked(20);
    vector<double> score(20, 0);
    rep(i,20) {
        int t = today();
        asked[i] = ask(1+i);
        score[i] = asked[i].size() + 0.05*(99 - (pre+i+1));
    }
    priority_queue<pair<double,int>> pq;
    rep(i,20){
        pq.emplace(-score[i], i);
    }
    auto a = pq.top(); pq.pop();
    int keep = a.second;

    rep(i,post-1){
        int t = today();

        auto a = pq.top(); pq.pop();
        int v = a.second; double sc = -a.first;
        say(1+v, t);
        ++sc;
        pq.emplace(-sc, v);
    }

    int t = today();
    say(1+keep, 100);
}

int main() {
    int T; cin >> T;
    for(int z=1; z<=T; ++z) {
        testcase(z);
    }
    return 0;
}

New Elements: Part 2

(あとで書く)
→WA(n)

終了後

こちらもdoubleで計算したのが敗因?と思って有理数にしてみたけどWA
あとで調べる

Contransmutation

(あとで書く)