ICPC 国内予選 2020 参加記
結果
ICPC 国内予選 2020 にチーム「tsutaj」で参加しました。 ABCDE の 5 完で、全体 18 位、学内 1 位で予選突破しました。
本記事では時系列に沿ってタラタラと思い出を語ります。
3 年前(2017)
学科紹介で ICPC を知る。 とりあえず出てみるか 順位:204/358 まぁそりゃあね
2 年前(2018)
1 年間準備をした。大学生活の全てを競プロに費やしていた。 学内 2 番手と言われるチームで ICPC に出場した(1 番手は tsutaj, TAB, えびちゃん の four-t)。
結果は学内 3 位で敗退 どうして...
1 年前(2019)
過ちは繰り返す...
学内 3 位、敗退...
半年くらい前
tsutaj が卒業するので、TAB、えびちゃんにチームに入れてもらう。 偉大な先輩に最大の敬意を込めて、チーム名を「tsutaj」にする。
定期的にチーム練をしたりした
1 ヶ月前
かなりチーム練をした気がする。 2 週間前くらいから、土日全てを返上してチーム練していた。
前日
前日の夜に突然、顧問から電話がかかってきて、一緒に松屋に行った(どうして?)
当日
A が monkukui、B がえびちゃん、C が TAB でやる。
A より先に B が AC される(えびちゃんはやすぎない?)
1 分後くらいに僕が A を AC する。最初、2020
だけでなく、1010
とか 5656
とかでもいいかと勘違いしていた。(焦りすぎ)
C を TAB がつらそうにしているので、少し問題文を読んだけど、僕が苦手な問題っぽい。TAB 君を信じて任せる(ごめんね)
D が構文解析なのでえびさんに伝えると、「やったー、わーい、えへへ」みたいなことを言っていたので任せることにする。
E を読む。
見当はずれな DP を思いついて、Slack で解けたと発言したり、解けてなかったと発言したりして、かなり迷惑なことをしていた。(焦りすぎ)
この時点で学内 3 位だったかな?ICPC のトラウマが蘇る。今年も敗退か...
TAB 君が愚直に近い解法で 15 分くらいで PC を回して、C を AC してくれた。ありがとう。
えびさんが D をつらそうにしているけど、えびさんを信じて放置(ごめん)
TAB 君に E を相談すると、流れるような考察ステップで見事に計算量を落としていく 痺れた
「60 * 60 は 行の偶奇に分けると 30 * 60 になるね」
「市松模様は二部グラフで、頂点集合ごとに独立に解けるよね、15 * 60 になった」
「一列ごとに bitDP ができるね、遷移は 215 * 215 をするとやばいけど、部分集合を列挙するいつものテクを使うと 315 になるね」
この考察を盛りなしで 3 分でやってた。TAB 君すごすぎ。
TAB 君は考察担当ということが決まっていたので、E の実装を僕が引き受け、TAB 君には D に加勢に行ってもらう。
D はえびちゃんが途中で何かにひらめいたっぽくて、TAB 君はそれを信じて F に行ってた気がする(E の実装に集中していてうろ覚え)
間も無く D が AC されて、えびちゃんすごい
本番で構文解析が AC できて、努力の賜物です。
E がバグったことを報告し、すぐさまコードを共有した。
えびちゃんはデバッグが得意で、ここが怪しいとか、ここで配列外参照をするとかたくさん指摘してくれる。
指摘されたところを直すとサンプルが合うので実行する。なかなか終わらないな〜と思っていたら、えびちゃんがパラレルで実行してくれていたらしく、PC スペックの違いを感じる。
E 通ることをお祈りしていたら、 えびちゃん「あ、E 通ってますね」みたいなことを発言していて、なんかよくわからなかった(順位表を見てたくさんの人が通しているのか、僕の E が通ったのか)。
TAB 君が F を解けてるっぽくて、実装を頑張っていた。
「果敢にも、GH に挑戦するか、F の愚直を書くか、どっちがいいですか?」とか発言したら、「愚直を書いて」と言われたのでそうした。
E を通して興奮していたので、問題文が 10 分くらい頭に入って来なかった ごめん
F の愚直が書き上がる
F は提出するも WA
残り時間が 5 分だったので、generator を書いてる時間はない。手で Hack ケースを探していると、
1 0
で RE していることに気がつく。
TAB 君に伝えて、提出してもらうと、
the contest has been over
みたいな表示がされてて時間切れ。もし通ってたら全体 5 位だったと思うと悔しいので、落ちててほしいね みたいな話をした。
まとめ
「2 度あることは 3 度ある」で、3 回連続国内予選敗退していた。今年は「4 度目の正直」で突破できたので、ものすごく嬉しかった。 アジア地区予選に出場するのは初めてなので、オフライン開催されるといいなぁ いろんな人と交流したい。
応援ありがとうございました。