ICPC国内予選2021参加記

ICPC国内予選2021にchomonolisとmizu_yokanの二人とチーム「Cutting Tree」で参加しました． 結果は4完27位で，予選を通過しました！

本番まで

本番までに構文解析をやっておきたい&&実装力を鍛えたい気持ちがあったため，ASCII ExpressionとMatrix Calculatorを通すなどしていました．

前日（木曜日）にチームメンバーで集まり，リハーサルをしました．ボス問である鎖中経路の実装がすぐにできず，悲しい気持ちになりました．

本番前日の夜は緊張でなかなか寝付けませんでした．酔っ払ったら/お腹がいっぱいになったら眠くなるだろうとストロングゼロ+炭水化物を摂取したり，運動して体力を使おうと深夜の大学を徘徊したりしたんですが全く効果がなく，自分で自分にキレていました．

幸い本番当日は予定が何もなかったため，昼過ぎまで布団の上で過ごしていました．

その後大学へ向かい，15時半ごろにチームメイトと合流しました．

予選開始までに1時間くらい時間があったのですが，その間は会場に遊びに寄ってくれた同じ大学の競プロer達と雑談をしたりしていました．

本番

前日の打ち合わせで，初動はA,B,Cをそれぞれmizu_yokan，僕，chomonolisで分担すると決めていたので，Bを読みました．

一瞬何やこれとなったんですが，落ち着いて読むと，左端の列に数字が書いてある時，その数字が書いてある行の値が確定することがわかります．また，あるマスに数字が書いてある時，そのマスの列/行の値がわかっていれば，行/列の値もわかります．そのため，盤面全体を走査し，行/列の値を一つずつ確定していくコードを作成しました． 実行に数十秒程度かかってもいいからバグを埋め込みにくいコードを書くと決めていたので，愚直に100*100のマス目全体を見る処理を100*100回繰り返すコードを書きました（今気づいたんですが，繰り返し回数は高々200回で良いですね…） 入力がw，hの順に与えられることにしばらく気づかず時間を溶かしたりしつつ実装を終え，ちょっと待つと実行が終わりACできました．ほとんど同じタイミングでmizu_yokanによってAが通りました．

Cに構文解析要素があるとのことだったため，見ます．chomonolisがすでに考察を終えていたため，それを聞いて実装しました．文字列から木を作成し，答えを根の全探索によって求めるコードを書きます．巨大なテストケースに対してめちゃくちゃ時間がかかり焦ったのですが，メモ化をすると爆速で処理が終わるようになりACできました．

その後，三人がかりでDを見ます．本当に何も分からなくて「焼きなましじゃない？」みたいなことを言っていたら，chomonolisが二分探索+半分全列挙解を完成させてくれました（すごい…）．それが想像以上に高速だったため，PCを応援しつつ処理の完了を待ちます．その後しっかりとDが通り，4完が確定しました．

その後，Eをチラ見し「難しそう…」となったため，予選終了までは順位表を眺めたり，各問題の振り返りをしていたりしていました．

個人的な感想/反省点

はじめてICPCの予選を突破できたため，本当に嬉しい気持ちでいっぱいです．

今回のICPCでは数十秒~数分程度の解法ができたら，無理に高速化せずにそのまま実行しようと決めていたのですが，（去年のICPCで，数十秒で実行が終了するプログラムの高速化に固執してしまい予選突破を逃した思い出があったため）それがいい方向に働いたな〜と感じています．

また，今回のC問題では考察と実装の分担がうまくできたため，個人的にかなり良かったです．

反省点として，実装が遅かったなあというのがあります．特に，Bに30分近くかけてしまったため，もう少し早く書けるようになりたいです．

アジア地区予選も頑張ります！

chomonolisによる参加記もあるため，ぜひこちらもどうぞ！