クマーの競プロ精進日記

AtCoder赤とICPC World Final目指して頑張ります.競プロ自戦記、アルゴリズムなどについて

ICPC2021国内予選・チームSPJ視点

上位23チーム中唯一Dが解けず,ABCEFという摩訶不思議な5完で敗退したあの敗戦から1年.今年もこの季節が来た.さすがに去年は3人とも競プロ歴が浅くて勝てるとは思っていなかったが,今年は十分にチャンスがあると3人とも確信していたと思う.

チームメンバー

つちのこ (AtCoder: nok0 - AtCoder (黄), Codeforces: nok0 - Codeforces (濃橙, max: 薄赤))

twitter.com東大教養学部2年(工学部物理工学科内定).アカウント名はノックゼロと読む.タイピングがチームで最も速く,主に重実装問題を担当する.私が「大丈夫?ほんとに1人で通せる?まじで??」とめちゃくちゃ心配するような重い実装問題でも颯爽と書き上げてノーペナで通すすごい人.3人の中ではTwitter上で一番名前が知られてそう.いつもA問題をやる.

 

zkou (AtCoder: zkou - AtCoder (黄色, max: 橙), Codeforces: zkou - Codeforces (薄橙))

twitter.com東大教養学部2年(工学部計数工学科内定).本人はゼットコウと読まれるのを想定していたそうだが,皆ずこうと読んでいる.チーム内で唯一メイン使用言語がPython.天才構築問題がかなり得意だがICPCにあまり出ないのが辛いところ.構築以外でも何かと天才性を発揮するのであまり実装には参加せずに考察を詰める役割.この人とつちのこが協力して数え上げをやると仕事が本当に速い.いつもBをやる.

 

クマー (AtCoderKite_kuma - AtCoder (橙), Codeforces: Kite_kuma - Codeforces (薄赤))

twitter.com

東大教養学部2年(工学部計数工学科内定).筆者.3人の中で最もAtCoderのレートが高く,かつコンテストの爆死が最も少ないので一応安定枠っぽい感じの人.構文解析と幾何を担当する(できるとは言っていない).構文解析は他の2人も書けるけど幾何をできるのが私しかいないので幾何が出るとぼっちになりがち.いつもCをやろうとするものの,実装がめんどくさくて結局つちのこに投げることも多い.じゃあ何ができるんですか?知りません…

 

 

開始前.3限の授業を終えて事前にお願いして借りていた教室に移動する.15時から20時まで貸切.

 

セットアップ作業を終えてもまだ開始まで結構時間があるので,それぞれ喋ったり寿司打をしたり音ゲーをしたり寝たりして思い思いに過ごす.緊張感が高まってくる.今年も不必要に東大の層が厚いので,抜けられるかどうかはちょうど半々くらいかなあとぼんやり思っていた.東大なら通過には10位以内がほぼ必要十分条件と言っていい.去年は東大のとあるチームが12位で許されていたが,かなりレアケースと考えてよさそうだ.

 

開始.つちのこがA,zkouがB,私がCを読む.ABを2人がサッと通す.あとで見返したら最速の2完だったらしい.これは余裕がありそうだと思いつつCを考えたがなんやこれとなる.構文解析は私の担当なのでとりあえずパースして木を作る.他の2人はCよりも正解者が多いDに行っている.まだパースが終わっていないが,Dが有名問題っぽいのに落ちたというので見てみる.2分割なら有名なNP完全だよねという話をしたらつちのこが トータルで50^5くらいのDPを思いついたので解決.私はCに戻る.Cのパースが終わり,やばそうな全方位木DPが思い浮かんだもののCでそんなめんどくさい問題でるのか?と思って別の方針を考えた.結局ひとまずO(N^2)の木DPを書いて自分のPCの速度に頼る方針に走った.書きあがったものの実行が全然終わらない.そうこうしているうちにDが通る.順位はこのとき7位とかだった気がする.Cがやっぱり全然終わらない.全ケース合わせると  6 \times 10^{10}くらいの計算量なのでまあ確かに遅そうだとなる.やはり全方位木DPしかないかとなる.zkouと一緒に実装を詰めるとなんとノーバグでサンプルが通る.おそるおそる出すとAC.自分の全方位木DPが古いライブラリだからあまり信用できずドキドキした.ひとまずノーペナで4完できたという事実を前にして落ち着いてくる.順位表を見ると上位のチームでCとEを通している割合が半々くらい.やはり今年も前半から結構辛い問題が並んでいるのだなと認識する.Eがもう書くだけだというのでFに行く.Fを見たら完全マッチングで,最近授業で習ったDM分解がすぐに思い浮かぶ.EがWrong answerになる.すぐつちのこが訂正して,投げる.Wrong answerになる.さすがにまずいとなって3人で一緒にデバッグをする.細かく修正しつつ慎重にコードの正当性を確認して,投げる.AC.この時点で8位,残りが80分.これで終わったらどれほど楽か….F~Hはどのチームにも通されていない.改めてFを見る.やはりDM分解で解けそうということになる.解法が詰め切られていないままつちのこがDM分解を実装する.zkouがそれを横からチェックする.私は最後にどうやったら全体を強連結にできるかのアルゴリズムを考える.意外とできない.引き続き考える.考える.たぶんここは落ち着いてやればそこまで難しくないパートなんだろうが,時間の切迫を感じて頭が舞い上がっている中で私は必死で考えていた.思いついた.zkouに確認して書き始める.残り時間が40分ほどしかなく,とても少ない.とにかく全力で書いた.つちのこのコードを繋げて動くか確認する.Segmentation fault を何度か潜り抜けて,サンプルの結果が合う.あとは投げるだけ.残りが2分ほどしかなく,ほぼラストチャンス.Wrong answer.懸命にバグを探すが見つからない.19時31分.終わった.Eを通して以降見ないことにしていた順位表を見る.11位.上には東大の4チーム.椅子から転げ落ちて,地面に倒れ込んだまましばらく動けなかった.

 

 

 

起き上がって順位表を見る.

f:id:kumakumatime:20211106003808p:plain

10位との差は900秒程度.15分…挽回のチャンスはあっただろうか.Cで愚直実行をやろうとしなければ,全方位木DPのライブラリがもう少し便利な仕様であれば(上には書いていないが,このせいで少し手間取った),Eのペナ1つ目で私が介入できていれば,授業でやったDM分解のライブラリを持っていれば,そもそも10位以内の他のチームが1つでもいなければ….タラレバを並べても仕方がないのだが,この結果はあまりに非情なものに感じられた.

 

順位表を見つめたまま放心状態の私を前にしてzkouとつちのこが帰る支度を始める.リロードしたら順位が変わるんじゃないかとか,そんなバカなことを考えながら何回かF5を押し,結果の変わらない画面を見届けてからPCをシャットダウンした.

 

さすがに今日は何か旨い物でも食うかとなる.結局大学前にあるハンバーグステーキの店に入って,いい肉を食べてお腹一杯になった.

 

寮に帰ったら他の寮生が気を遣ってくれてとてもありがたかった.悔しい負け方をしたときって自分一人でいるときは何とも思わないけど,直接対戦に関わっているわけではない人に優しくされると胸が一杯になってしまう.将棋の全国大会の決勝で負けて泣いたあの日以降,あんな思いは二度としたくないと思ったけど,またそんなときが来るとはな.覚えてろよマジで.