ICPC2020 国内予選 参加記
ICPC国内予選、eSeFとぽたてと一緒にチームchihominで出ました！
チーム形成の経緯
全員ICPC初参加です。eSeFとぽたては東大B2の付き合いです。3人は互いに顔を合わせていますが3人同時に居合わせたことは無い気がします。本番前は9月～10月頃の有志コンラッシュに出たり(chihomin結成がKUPC直前なので、KUPCより前は別の方々と出ました)模擬国内に出たりしました。それ以外のチーム練は学業を優先した結果あまり出来ませんでした。悲しい。
ちなみに、私とeSeFがC#使いでぽたてがC++使いなので、C++不慣れerに辛いICPCということで不安でした。
国内予選前
国内予選が始まる少し前に、りあんさんが国内予選のチーム自己紹介に色を付けてソートできるやつを作っていたので(すごい、ありがとうございます)見てみました。
各列が辞書順でソートできるようになりました、大学別に見たい時とかに使ってくださいhttps://t.co/bwfvloZCVN pic.twitter.com/0UalBSnZXm
— りあん (@rian_tkb) 2020年11月6日
これを見ると、なんと東京大学で自己紹介に登録しているチームの中でchihominは唯一暖色コーダーが存在しないチームだそうです。しかも私はその中で唯一の水色コーダーでした。ひえ～～～～～～～～～～～。もちろんこの自己紹介に登録していないチームもいるので暖色がいないチームは東大にもまあいると思いますが、東大でICPC予選を通過する厳しさを垣間見ました。
本番
16:30 ICPCのコンテストサイトに繋ごうとするが、何故か繋がらない。めっっちゃチーム全員で焦りまくりました。eSeFが審査員に電話すると、「ただいま電話に出られません」と言われたそうなので、他のチームも同じだろうと分かりました。落ち着いて待ちます。なんか途中でリハーサルの問題が出たので私が「もう一回リハの問題を解くか～」って茶化したら2人に「いや怒られるでしょ」って冷静になだめられてかなしくなりました。
16:40 コンテストサイトが戻ります。喜んで問題に取り掛かります。弊チームは初動ではレート順(私→ぽたて→eSeF)にABCを見ることにしているので、私はAを見ました。すぐ分かったので実装します。
16:45 AをACします。
16:49 ぽたてがいつの間にかBをACしていました。
16:55 ここらへんでCが難しそうって聞いて一緒に考えます。高速素因数分解があればゴリ押せそうと私は提案し、事前にローカルにダウンロードしていたうしさんのライブラリ(Luzhiled's Library)に高速素因数分解があることを発見し喜びました。でもなんかeSeFが解けてそうなのでとりあえず高速素因数分解の話は保留にして任せます。
17:26 eSeFがCをACしました。早解きはそこそこ強いのがchihominの強みではないでしょうか。
そこから 詰まってきたので私は色んな問題を飛び回りました。Gをちょっと考察するけど通せそうにないため撤退、Hはまあみんな無理だろうってことで誰も何も言ってないのにほとんど話題に上がりませんでした。ということで比較的簡単そうなDEFをみんなで考えます。この時はD・EのACが多かったのでDとEをみんなで考えていたと思います。
E。私はみんなの考察を聞きながらD・Fを考察していたのであまり分かりませんが、2人が最小頂点被覆問題ってどう解くんだっけって言うので、私は蟻本を見て「蟻本だと二部グラフなら最大マッチングに帰着」と答えました。あと隣接しない頂点の選び方を聞く問題とかあったよね(Virus Tree 2)とか色々話します。でも嘘っぽそう。
D。構文解析は書いたことほとんどないと口を揃えるchihominですが、構文解析パートと本質問題パートで実装を分ける方針を取り、とりあえず本質問題の解決を試みます。私は式木の不等号ノードn個についてO(2n)全探索ではないかと提案。
だいたいここらへんで18時を迎えます。高難易度で詰まってチームの雰囲気が冷えまくります。いつもならここらへんで何かの問題を通せそうな兆しが見えるのに今回は全く見えなかったので焦りまくります。
18:20頃 私はFを考察していて、Undo付きUnionFindなら普通にシミュレートして通せない？と思います。色々議論して間違いを指摘し合ったりして、Fを実装することにします。またこの間2人はDの実装を分担していました。どうやらeSeFは解法1がほぼ分かったっぽいので私はDは2人に任せてFを全力でコーディングします。同時コーディングってすごい。
終わり際 2人はなんか微妙に合わないっぽいのでデバッグ。涙。私は終了10分前にFを実装しきってサンプルも合ったので投げるもWA。チームで歯が立たない感覚を共有しながらもデバッグをしまくりまくるが間に合わず。
終わってから
Dは終了後にサンプルが合ったらしいけど提出できないからかわいそうでした。eSeFがC++で構文解析をすると無限にバグると泣いていました。とても良くわかります。ICPCでもC#使いたいです。
EはTwitterで天才解法が流れていたのでみんなでこんなのわからないよ！って言いまくりました。
Fは解法は間違いが無さそうなのにバグの原因が無限に分からないため本当にお手上げでした。ICPCでもC#使いたいです。
総評
3完ペナ3068分で56位、東大内13位/17チームでした。東大は強いチームばかりなので横浜に進出できるとは思っていませんでしたが、それでも全く振るわず納得できない結果に終わってしまいました。DとFどっちもACできそうでできなかったのがとても悔しい……。今後の課題は高難易度の問題をきちんと通すことだと思います。
チーム全員悔しさで競プロのモチベが上がりまくったため、来年は全員暖色になって2国内予選に臨んでると思います。対戦よろしくおねがいします。
