ICPC国内予選2023 参加日記

はじめに

　maracuya_sourのメンバーとしてICPCの国内予選を参加しました。

　チームはBasin(自分), kumastry(kuma), itohalというは緑緑茶で編成して、うち去年のICPC参加の経験者は自分だけでした。チーム構成は学年+言語で決めて、言語としてはPythonを選んだ。

前日まで

　ICPCの二週間前までには個人練で週2ペースでAtCoderのバチャコンとコンテストの参加(ABC難易度)を主に練習して、そしてチームでICPCの過去問を2回練習した。

　1回目には、皆がICPCの問題をなれるための練習であって、戦略には一切考えず、個人ペースで去年の過去問解いてみたうえ、できないところを相談しながらチームで実装する方針で練習を行った。結果的には90分でBまで解いた。

　2回目には前日の練習で、戦略や使用するコンピュータなどを決めた上で、2020年度の過去問の練習をした。その間に、問題文を印刷する戦略も決めた。結果的には3時間でCの実行が終わらない状態で、当日は3完できそうっていう気持ちだった。

当日(コンテスト開始前)

　十分な睡眠をとりました。そして自分が起きたら2020年度のCに粘着し、計算量を下がる方法が探したが実装する時間がなかった。

　11:00になったらリハーサル。自分はLを10分間で解いた。

　そして午後の三限には(コーチの)授業があるが、終わったらチームメンバーの提出練習を見守った。

　16:00ぐらいに会場に戻って、コンテストの物理的環境構築をはじめ。

コンテスト中

　前日が決まった戦略は、茶色コーダーが独自でA問題を解く途中で2人の緑コーダーがB問題の考察を始まるってことだが、問題文の印刷にはすごし時間にかかりそうなのでとりあえず全員がA問題に入った。

　A問題には2023と一番近い数字の添え字を表示する問題が、一番目の添え字見た瞬間で自動的にソート済みと思いまして二分探索の実装に入ったが、入力例全体にはあってないのでfor文でやりなおして10分弱でAC。

　B問題、最初には全員で考えたが、途中からitohalが全探索で解けそうと言ったので、完全に任せて2人の緑コーダーがC問題に突入。しかし、考えたアルゴリズムがあっていたが実装にはうまくいけず、WAがあった。修正してもACできない時点で自分が交代されて2.5時間ぐらいで愚直AC。この問題には、前日AtCoder会社のYouTube動画からヒントがもらえた。

　C問題、最初には自分とkumaで考えたが、自分はマンハッタン距離から45度回転という方向には考察をして、上手く行けなかった。同時にkumaさん行けそうなアイデアがあるのでいったん任せて飛ばした。B問題交代する時点でitohalもCの考察に入って、二人がぎりぎりまで実装が終わらなかった。

　D問題、自分が一人で考察する形になった。冷静ではない考察で部分和問題と同じ方針で行けるかと思った。そして制約には大きくないのでdpを書かずに、単純に前から要素を入れて、その時点の全部のあり得る得点を列挙し、次が必要な点数があったら何もしないって方針で入力例が全部あったが、提出するとWAした。そこからさらにdpを使って部分和の方針に進んで、そこでは単純に部分和作れるかではなく、作れるなら集合として表す方針まで考えたが、最後までには遷移が書けなかった。

コンテスト後

　少し休憩したあとに、他のチームと一緒に解説&アイデアの交流をした。コーチからCを奇偶に注目してって言われて確かに行けそうかもと思った。そしてDについては部分和になりそうが書く方針はなかった。代わりに行列木定理に関係あるかもっていう結論があった。

　そのあと、解説を見た。Dの素朴な動的計画法と書いて、耳が痛かった。また、7に抑えることがわからなかった。

感想と反省

　今年も負けました。けど、去年よりにはDは何やるかはある程度想像できて、いい成長になると思った。

　また、チーム全体のマネジメントが足りないと思った。例えば、Bの交代をもっと早くすれば順位がもっと上がるなっていう感想もあった。

　どちらかというと、今回は単純に問題を個人に分けて、個人個人でやるっていうことになってしまい、チームの交流が増やせば成績がもっと良くなるかなと思いました。