反省文

(真面目な話では) 初投稿です.

ICPC 国内予選2019に出場しました. 結果は3完113位でした.

チーム編成

研究室の競プロ好きとチームを組んだ.

僕

・AtCoder 水色

・ICPC 4回目

・2018 Yokohama Regional 出場 (FunamiYui)

・最近競プロから離れ気味

・C++

同期

・AtCoder 茶色

・といっても昨年コンテストに3回出ただけ

・国内予選2018に続き2回目

・謎解きが趣味 賢い

・Java

先輩

・AtCoder 緑色

・ICPC 初出場

・M2 なので最初で最後

・ルービックキューブが趣味

・Java

チーム名の "Kuu Neru Mazeru" はキャンパス最寄り駅の近くにある油めん屋が由来.

全員それなりに競プロをやるし出来るので, ICPC での3完は最初から期待できた. 数少ない学内競プロerの上位勢が固まってチームを組んでいたので, 我々はそれに続くことを目標にしつつワンチャン通過を狙う.

本番まで

チーム全員が典型に強くなかった.

5月は ABC の過去問からそれぞれのレベルに合った典型問題や200, 300で比較的実装量のある問題を選出してバチャ. 全員が解いた問題を解説することで問題を言い換えたり重要な考察点をあぶり出したりするという練習も兼ねた.

6月から ICPC や模擬の過去問に触れる. 一旦個人戦のバチャを行い過去問の雰囲気を掴んでもらった上で, 個人ではどれだけ詰めきれるかや実装出来るかを確認する. 僕は AOJ-ICPC の200以下はほぼ全て埋めていたので, 2人に解いてもらう問題選びはそれほど困らなかったし, 短期間に週1回集まって行うチーム練の内容としては良いものになったと思う. 僕個人では蟻本を読みつつ250～350を中心に埋めて, 3完をより確実なものにしつつ4完に手を伸ばそうとする. 6月終盤には1セット用意して実際に戦略を立てて取り組む. 4完できたのは1度だけ.

チーム練をしている間の戦略は, 2人に C までを任せて僕が D を読む, であった. しかしいざやってみると D は完全にガチャになってしまっていたので諦め, 本番1週間前を切った段階でそれぞれの担当を1問減らす. 2人が B を通すまで1時間位かかっていたので, 3完でも学内で普通に負ける可能性があったのも理由の一つ.

あと僕は何かと戦犯をしていた.

2人に伝えた最も大事なことは, よほど慣れた内容でない限りプログラムを脳死で書こうとしないこと. 実装の方針が明確に立っていないまま PC を触っていても思うように進まずもたついてしまうからだ. 例えば for ループ1つとっても, for ループを書くことが大事なのではなく, その i について何を解くのかを明確にする, ということ. とても大事なので前日にもそれを言いながら問題を考えてもらった.

前日は研究室の B3 歓迎会をしていたので全員飲酒した.

本番

2人の方は, プログラムを書くのは同期の方が早いので同期が A を開く. 同時に C を開き僕が C を読む. A はやるだけだったようで, すんなり AC. 9:27.

C は分銅を使って作れる重さが 通りあるのでそれをいい感じに左右に振り分けるとピッタリになる. この時点で嘘. 現在の分銅で測れない場合に何をすれば解けるのか全くわからない. かなり時間を溶かした.

その間に B が進んでいた. 考察に時間をかけていたが, しっかり詰まったであろう様子を感じ取ると先輩が vim でプログラムを書いていた. いつの間にか同期が emacs で書いていた. 何があったんだろう. ちらっと見ると BFS を書いていたので知って入ればやるだけの The B 問題っぽそう. C の進捗が無さすぎるので B 問題をちら見する. コンパイルエラーが出ていたが配列の length はメソッドではなくフィールドであると僕が指摘する. 直して実行すると答えが微妙に合わない. 問題を見ていたので OK ボタンを考慮していないことにすぐ気付いたため指摘, 直してもらって AC. 1:02:25.

3人で C を考えていく. 同期がかなり疲れていた. 僕が問題概要とわかっていること (嘘) を伝える. 同期が解の候補を全列挙出来るかと聞いてくる. ここでようやく嘘に気付く. 気付いてからは早かった.

状態はどう考えても左の皿と右の皿と置かないからなる 通り. ある状態において薬品を左に置くと仮定し, 左の分銅の総和 と右の分銅の総和 を考えると, 解の候補は で一意に定まる. したがって に対する解の候補も 通りになり, これを全列挙しても 通りであるので良さそう. に対する解の候補はユニークであってほしいので set を使い保持, map でその候補の個数をカウントする. カウントが に一致する最小の値を答えとすれば良い.

これをそのまま実装するとサンプルの2個目が合わない. そこでは, 追加しなくても測定可能で, かつ測定可能な状態を除くと実際には最適となる分銅を追加しても測定できない薬品が存在していた. 最初の段階で測定可能なものは解の候補の列挙から外せば良い. ここのリカバリも我ながら上手だった. 直してテストケースの実行に入ると時間がかかった. 計算量が なのでテストケースが100個あっても現実的な時間で終わると信じる. 終わった. AC. 1:51:16.

以下のコードは本番中に書いたものを思い出しながら書いたので, 多少異なる部分はあるかもしれないが処理手順は全く同じはず. あとなんか怖くなって #define int long long をしてしまったがどうせいらない.

#include <bits/stdc++.h>

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

signed main(){

    while(true){

        int n,m;

        cin>>n>>m;

        if(!n)break;

        vector<int> a(n),w(m);

        rep(i,n)cin>>a[i];

        rep(i,m)cin>>w[i];

        int A=pow(3,m);

        vector<int> l(A),r(A);

        rep(i,A){

            int t=i;

            rep(j,m){

                switch(t%3){

                    case 0:break;

                    case 1:l[i]+=w[j];break;

                    case 2:r[i]+=w[j];break;

                }

                t/=3;

            }

        }

        int cnt=0;

        bool f[n]={};

        rep(i,n){

            rep(j,A){

                if(a[i]+l[j]==r[j]){

                    cnt++;

                    f[i]=true;

                    break;

                }

            }

        }

        if(cnt==n){

            cout<<0<<endl;

            continue;

        }

        map<int,int> map;

        rep(i,n){

            if(f[i])continue;

            set<int> set;

            rep(j,A){

                set.insert(abs((a[i]+l[j])-r[j]));

            }

            for(int x:set)map[x]++;

        }

        int ans=1ll<<60;

        for(auto e:map){

            if(e.second==n-cnt)ans=min(ans,e.first);

        }

        if(ans==1ll<<60)cout<<-1<<endl;

        else cout<<ans<<endl;

    }

    return 0;

}

続けて D に入る. 区間が 個ある. 一度に取れる範囲が決まってないのでどうすれば最小回数で達成できるかが全く思いつかない. 同期が回復するが僕と先輩の集中力が削がれていた. なんかそれっぽい感じの手法がいくつか出るも詰めきれず. 何もわからん.

終了

研究室に戻ったら誰もいなかった. お疲れ様の雰囲気で3人でしゃべる. 僕が時間を溶かしたという罪は重いが, それでもノーペナだし学内2位になれたので悪くはないとか話してた. 終了後配信をちょっとだけ見るも3人とも早く帰りたかったので, A の解説が始まったあたりで研究室を出る.

反省

とんでもない嘘を生やしてそこから何も進展しないときに振り出しに戻れないのは流石にヤバい. 多少前日の疲れがあったとはいえ調子に影響するほどでもなかったのに, C ですら2人の力を借りることがなければ解けなかったのは ICPC 4年目としてどうなのか. しかし, それが出来るのがチーム戦でのコンテストの醍醐味の1つであり, それをもっと難易度の高い問題で出来るほど実力がないのだからある意味良かった. 目標であった2位になれたことで, 後に学内で (こぢんまりと) 表彰され図書カード5000円分を得られるので得した. どうしようもない欲を言うと, 111位を取れればレトリバさんから企業賞を頂けたのでちょっと惜しかった.

相対的な実力から僕がチームの主力となってあれこれ教えてきたので, 2人がそれなりに満足していた様子を見て安心した. ICPC は学科でのお祭り的存在でもあり, やっぱり楽しいと思える3時間を過ごせた.

来年はどんなチームを組むのだろうか. 今年組んだ同期とは組む可能性があるが, あと一人はどうなるか. 1位となったチームも一人引退なのでややこしくなりそうだ. とにかく1位のチームはアジア (横浜) で昨年以上の活躍をしてきてほしいし, 僕らはこれまでどおりのんびり競プロと向き合いつつ, 他の好きなこともしながら卒業していくだろう.

追記

https://t.co/g6PbCbSpVR

プログラミングコンテストを通じてミルキィホームズの名を語り継ぐ存在になりました. 1人のミルキアンとして, 1人のホームズ探偵学院生としてこれほど名誉なことはありません  (？).