ICPC2021国内予選参加記

はじめに

　2021年11月5日に行われた2021年 ICPC アジア地区横浜大会 国内予選に北海道大学のチーム「kamaboko」として参加して総合順位39位となりました。この記事を作成している11月6日現在、国内予選通過チームの発表は行われていないですが、大学内順位が1位なのでおそらく通過していると思います。

チーム作成の経緯

　私は現在学部4年生で、1年生の時からICPCに出場しています。今年は去年までの3年間チームを組んでいた先輩が引退になったこともあり、完全に新しいチームを組むことになりました。私のサークルでは、どのチームにも所属していないAtCoderのレート（のhighest）が最高の人をリーダーとして、まだチームが決まっていない好きな人をチームメンバーに選ぶというドラフト方式で（上位3）チームを組みました。私がリーダーに選ばれたのは3番目で、単にレートだけを見ると学内では3番目の実力ということになっていました。また、去年から活動がオンラインになっていたこともあり、ほとんど面識が無い人とチームを組みました。

国内予選まで

　私のチームはメンバーがB4、B4、M1という忙しい構成だったこともあり練習時間は多くは取れていませんでした。基本は週2回のサークルでの活動（これでも中々全員は揃わなかった）で、それ以外は会津合宿の時にこのチームで1日出たくらいでした。そのため、細かい役割分担が決まっていたというわけではなかったのですが、自分以外のメンバーからは「実装が苦手」との自己申告があったので重実装は自分がやろうかな～くらいのことは考えていました。

国内予選本番

　（厳密には違うかもしれないけど）チームの初顔合わせ。PCスタンドと外付けキーボードを持ち込んでいるチームメイトを見てすごいな～とか思っていた。とりあえずABCそれぞれ1人1問担当しましょうという簡単な作戦だけ決めて競技開始になりました。
　Cを読むとなんか大変そうだなぁという気持ちになる。入力を見ると構文解析パートがあるので自分がやるしかないと確信する。入力からグラフを作ったりしてる間にAに2ペナが付いているのを見る。これはヤバいなとは思うも、もとから学内3位のチームだったのもありそこまで焦らずにCの実装を順番に詰めてました。
　気付いたらAとかBが通ったらしいので、順位表を確認してみる。なんだかんだ学内順位は3位ではあった気がする。CよりはDが明らかに解かれていたのでチームメイトの2人にDを任せてCをひたすら詰める。細々としたバグはありつつも解が完成する。遅いのは分かっていたがいつまでも実行が終わる気配が無いのでとりあえず回しながらDの話を聞きつつ高速化を考えてました。
　全頂点を根にしてDFSってことで、全方位木DPみたいなやつをしないといけない考察はできていたけどどう実装するか…になっていた。Dの方は色々と解法が出ていたようでペナが付いていたものの考察が進んでいるっぽいので任せたままCを考える。それぞれの頂点の次数が高々3なのでどの方向から見た時の値だよって情報を持たせてメモ化っぽいことをするといけるんじゃねと気付く。辺の張り替えとかで少しバグらせるも実装できて、実行も爆速で終わる。このタイミングでちょうど遅い解法の実行も終わっていたので結果を目で比較して合ってることを確認して提出。ACが出てかなりほっとした。
　3完の時点でペナルティが厳しかった記憶がある。学内順位は2位になってたけど、3位のチームが1問通せばいつでも逆転されるくらいペナが付いていたはず。Dは愚直をとりあえず回してもらいつつ、ちゃんとした考察が生えていた。自分は全然理解してなかったけど、とりあえず話を聞いて（理解してないけど）いけるって伝えて実装してもらいました。そうやって作ったやつの解が愚直と（そんな大きくないケースでは）一致しているのを確認して提出し、ACがもらえました。この時点で学内1位。
　Dを通してあまり時間がなかったのと、Eの考察もそこまで生えてなかったので残り時間はEの考察をまったりしていました。Eの合ってそうな考察が生えたくらいのタイミングでコンテストが終了し学内1位で終了でした。

おわりに

　3回目の国内予選通過が濃厚です。自分がC通せたの大きかったなぁと思いつつ、自分が触った問題がCだけだったのもあってチーム全員が貢献できていた感じで良かったです。本番での問題担当の分け方とか、ICPCの国内予選通過を目指した立ち回りが上手くいったと思います。

special thanks