ICPC2020国内予選参加記

ICPC2020国内予選に参加しました！
チーム「Simulated Annealing」はpaotan、hexa0611とcirno3153で参加し、4完44位で予選通過です。

当日の流れ

06:00
大学で合流する流れになっているので出発。
眠いようなそうでもないような不思議な感覚だった。

09:00
到着、雑談したりしながら待機。

11:00
リハーサル開始
とりあえず本番と同じように最初の三問は順に解いてもらうことにし、自分は3問目の問題を読むことに。
一度は本番でDifferent Programを試すべきだよねーってことで、全員空白を入れたり改行増やしたりして試しつつ通す予定でした。
先頭2問はすぐ解けたみたいだけど、3問目の解法が全く分からず。黄色コーダー辞めた方が良いのでは？
誤読してた……書き直してAC、この段階でリハーサル一位だった模様。みんな早朝起きれないのか？？
まぁなんかその後は皆で鎖中経路を考えるけど全く解けず、リハーサル9位で終了。
この順位を本番で出せればアジア確定だよねーとか、黄色コーダーがいるはずの理科大チーム「Re.rooting」には勝ちたいよねって話をしたりしながら待機。

16:30
開始、まずはF5を押して画面更新。
「no status information for team 464689 in contest are found (database broken or not initialized?)」
……これはなんですか？
フリーズするも、まずは自分たちのチームだけこれなのか全員がこれなのかを確認する必要があると考え、チームにこの画面のスクショを取る(もし自分たちだけの不具合だったときに審判団に抗議するための証拠作り)と同時に緊急用電話番号を引っ張り出し、電話を掛ける。つながらない、終わった──。
もう1回掛けても電話が混み合ってたので、流石に他チームも入れてないでしょって思った段階で何故かリハーサル画面が表示される。
あー、リハーサル画面ならclarを通じて状況説明できるものね、遅延連絡を送るためかなって思いながらF5を適度に押してたら、何故か本番問題が表示された。は？？？？？

16:40
担当問題を解く。
Aはpaotan、Bはhexa0611、Cは私が担当し、終わった人からD以降の解けそうな問題を考察する方針になっていたので、まずはCを開く。

C問題
が与えられるので、を満たすのうちの最小値を求めよ。

……え、解けない。マジで解けない、詰んだ──。

17:05
paotanがAを16:43に、hexa0611がBを17:03に通してたので、いったん呼び止めてCを解いてもらうことに。
その間に自分も愚直解を書いて実行するが一生結果が出力されず、これダメだねって気持ちになる。

17:40
hexa0611がCの解を10分ほど出力させて提出したらCorrect Answerが出たらしいので一安心、そのままData2をACしてもらうように頼んでDを読み始める。
このとき、まだ私は一問も解いてなかったので完全に戦犯では？という気持ちがあり、すっごく心臓に悪かったです。

17:50
Cが通ったらしいが理科大ほぼ最遅、もしかしたら5完しなければ負けるのでは？？みたいな話と戦いつつ考察。
D問題は構文解析に見えるけど全然違う問題で、minとmaxで構成された式が2つ与えられるので、その式が同値になるような変数の順序付けが何通りあるか求める問題。
制約のは明らかに愚直を落としてを要求してるので、まずはbitDPできないか検討。

18:00
集合で考えても状態数が不足しててまともにDPできないので、解法IDA*で考え始める。
片っ端から考えられる解法(bitDPをする、遷移を大小関係にしてみる、答えを決め打つ、半分全列挙する、辺を貼ってグラフにする、式上の最小値から決め打つなどなど……)を検討キューに入れ、適当な時間で切り替えつつで反復深化深さ優先探索を開始。
考察を片っ端から口に出して何かないか探し始める。

18:15
paotanに、答えを決め打つ方針で解けない？って言われたので再検討すると解ける、勝った。
さっそく構文解析を実装開始、万が一にもバグらせないようJavaで書き、ちゃんとtoStringをOverrideして式が受理できてるか確認したりなど念入りにデバッグしながら実装。
途中、これ答えと式が一致する時って幾つ加算すればいいんだっけ？って聞いたら一瞬で決め打った集合それぞれの階乗が答えだと返ってきたの本当助かる、考察に集中したいから数学パート全部チームメンバーに投げることを決めていたので。

18:30
実装完了、サンプルも一致したので動かす。
なんか遅いけどまぁ全部出力されれば行けるやろ、の精神でEFを読み始める。

18:40
流石に遅すぎない？
これだと19:40までに出力終わらないので、いったん止めてあっちこっちにデバッグコードを挟んでどこがボトルネックか調べる。
……何故か最初に構文木を作るところがボトルネックらしい、よりにもよって全探索ではなく構文木のところにボトルネックってなぜ……？

18:50
何故かfor文で文字を受理するところで左右の木を作ってた、指数オーダーになってて草。これ模擬国内Eでもやったミスじゃん
直したら爆速、そのまま提出してAC。
ここで理科大の他チームを見たらまだ3完、とはいえ時間の差が大きすぎて相手チームはどのタイミングでも4完したら順位ひっくり返せる模様。
流石に怖いので、5完して絶対負けない順位にしようという話になる。

19:00
E問題の方針を聞くも解ける方法が思いつかず、Fはグラフ問題らしいのでそっちを見る。
制約小さいなー、愚直だとおそらく実装20分に実行20分で終わるはずって見積もったけど、これはギリギリ間に合わないので想定解を考えることに。
まぁ辺を切る話だし逆順に見てUnionFindするか、あるいはこの間のCodeforcesで出題されたように逆マージテクをやるのが良さそう？
チームメンバーが逆順で実装する場合の手順を教えてくれたので、それを信じて実装する。

19:20
サンプル合ったし提出するもWA、バグに気付いて直すもWA。
実装を10分ほど確認してもバグのある気配が無いので、これは問題誤読していないなら考察が偽ですねって言ってたら終了。
最終的に理科大の他のチームは3完だったので、無事にアジア予選へ通過！
ところで順位確認したら28番目で通過だったので、これ理科大チームに負けてても通過だったね……？

全体の感想
C問題解けなかった時点で大戦犯を覚悟していましたが、ICPC考察担当である自分の考察力を信じたらDが通ったので満足です。いや嘘、やっぱりC通したかった。
やっぱり自分は考察が得意で実装はかなり苦手なので、アジア予選の時にはもっと自分が考察を多く回し、実装はチームメンバーを信じる形式にしようかな？と考えたり。
なんにせよ、チームメンバーの2人はありがとうございました！君たちがいなかったら予選通過できなかった(具体的にはCが通せなかった、Dももっと時間掛かったと思う)ので、とても良いチームワークだったと思います。
アジア予選楽しみ～。3月だっけ？