okimochi ICPC2019 模擬国内予選 参加記

参加資格ありのチーム内で5位！チームとしての上限に近いパフォーマンスだったと思う。

Aをまず通す。その間にBは01bfsやるだけですと言われたので受け取り、難なく通す。少しバグらせたのでここまで15分くらいかかってしまったが、そこそこ早かったようだ。

一方Cが怪しいながらもこるとんが書き始める。その間にDとEを読み、EがすぐにはわからないのでDがわからないというrisujirohにEを投げる。数分でEの解法が分かり(早い…)、Cが通らないらしいのでrisujirohがEを書き始め、僕がC、こるとんがDを見る。EがバグったがこるとんがDがいけるというので交代する。その後DとEを交代しながら連続で通しきる。なんかEはbitsetの宣言がよくなかったらしい。

その後、Cが注意力だけどいけそうという気持ちになる。1回WAを貰ったあと(ごめん)テストケースを見られることを思い出し、落ちているケースを探す。(0,奇数)みたいなケースが考慮できていないとわかり、実装して通す。ここまで90分で、8位くらいだった気がする。

ここから苦しい時間が続いた。Fは誰もわからないので捨て気味に。Hをこるとんが考えて、Gを僕とrisujirohで検討する。凸包から始めて、何らかの探索をするという方針まではrisujirohが立てていた。risujirohが幾何テンプレを書いている間に、詳細な方針を考える。凸包のアルゴリズムが動いていそうなことを確認した後、再度方針を立て直す。ここはかなり苦悶したが、｢上位K番以下は持たなくてよい｣ことに気づき、bfsを提案する。よく考えると｢探索の深さはKまででよさそう｣ということもわかり、計算量解析は怪しかったがrisujirohが不可能実装ではないと言うので実装に入ってもらう。僕は隣で見ていた。実装方針に悩んでいたので、priority_queueを用いた方針を提案。受理されるが比較関数を渡すのがうまくいかず(僕はそういうときは構造体を書いているのでそうじゃないときにどうするのかわからなかった、だめ)、risujirohがsetならわかるというのでsetでやることに(なにこれ)(重複除去を勝手にやってくれるので結果的にはよかった)。この辺からHを諦めたこるとんも加わり、3人体制で実装に入る。bfsパートはbfsだったのだが、探索を打ち切る実装が思いつかなかった。ここでこるとんが探索の深さを明示的に管理することを思いつき、書ききる。サンプルを試すと-1の処理を忘れていたので追加し、再度サンプルを試すと合う。やるしかないのでテストをダウンロードして実行すると爆速で終わり投げるとテスト1が通る。｢これ通ったらやばい、マジ…？｣とか言いながら興奮気味でテスト2を投げる。通る。さすがに嬉しくて3人で肩を組んだ。

残り10分とかだったので終わりムード。順位表を見たら6位(上に参加資格なしのチームがいた)でよかったのではという話をしつつ反省会した。

今日はチームとしてとても良く動けたと思う。CDEは誰かができないというものを他の人が1問ずつしっかり通した。Gは誰かが欠けていたら通らなかったと思う。これなぜか全くバグらなくて1発で通ったのかなりすごいと思う。Gは2チームしか通っておらず、FAもとることができた。2チームしか通ってないので作戦ミスにも見えるが、あの状況でGに振ったのはチームとしては正解の選択肢を取れたと思う。一人ひとりが力を発揮できるセットで、チーム戦ならではの瞬間が多くあり、充実した3時間だった。

個人としてはABを比較的すんなり通せた(Bはもっと早く書けたはずだが)。Cをしっかり通せたのもよかった。Gの解法にも貢献できて、自分としては十分仕事ができたかなと思う。あと2週間で少しでもできることを増やしたい。

結果的な順位はよかったが、模擬国内予選に参加していなかったり、人が揃っていない有力チームが複数あるので全く油断できない。でも、このタイミングで良い感触を得ることができて本当によかった。本番はせめて、｢これでだめなら諦めがつく｣くらいのパフォーマンスを出したい。