ICPC2022国内予選参加記
ICPC2022国内予選に torisasami、tokusakurai とチーム DELIAIR として出場して7位（学内4位）を取ることができました！ 正式発表はまだですが何もなければ予選突破です！！！ 僕個人としては ICPC 3回目の出場で初めて予選突破をすることができたのでとても嬉しいです！
正式に予選突破が決まりました。また他の2人の参加記はこちら tokusakurai、torisasami (2022/07/15追記)
予選前日まで
4年生になってから少し忙しいことが多くチーム練の頻度は減っていました。 今年は東大から強いチームがたくさん出るようで不安だったのですが、模擬国内はそこそこの順位を取ることができて少し安心しました。
僕が構文解析を毎回担当していたのですが2年連続出題されていることもあり、構文解析の書き方を2人と共有しました。
直前の土日に、本番はチームでどこかに集まってはどうかという話になって、指導教官に相談したところ大学の教室を借りることに成功したので*1チームで集まって参加することになりました。 対面で練習をしたことがなかったのでこれが吉と出るか凶とでるか読めませんでしたが、より円滑にコミュニケーションがとれたので結果的にはよかったと感じています
本番開始まで
1時間くらい前には全員集まることができて、院試の話をしたり、他のチームを今から闇討ちするにはどうすれば良いか考えたり、誰がどこを担当するかを決めたりしました。 相談の結果 A が僕、B がtokusakurai、C 以降を torisasami が見ていくことになりました。
僕と torisasami が蟻本を忘れてしまったのですが tokusakurai だけしっかり持ってきていました。*2
個人的には去年より落ち着いていて良い状態で本番に入ることができたと思っています。
本番中
↓問題 icpc.iisf.or.jp
A は見た感じ簡単そうでしたが模擬国内で1ペナを出した前科があるので慎重にいきました。 端っこは考えなくてよく$v_i \neq v_{i+1}$なので特にコーナーケースはなさそうです。 少し入力でバグらせてしまいましたが無事正解することができました。
torisasami が C の実装を始めているようだったので D 以降を見ていくことになりました。 D が数え上げ、E が構築、Fが構文解析を含む最適化でしたが問題を読んでいる内に C を通してしまったようでした。 数え上げなら torisasami の方が得意なはずと考えて D を押しつけて自分は E に取り組むことにしました。
tokusakurai が B で悲鳴を上げていたのでデバッグのフォローに入ろうとしたらなぜか gdb が tokusakurai の PC に入っておらずキレそうになりました。 コードを送ってもらって自分の手元で gdb を走らせて無事バグを発見することができ B を AC しました。
少しして E がわかった気がしたので実装を始め、並行して手が空いた tokusakurai に E の構築成功か判定するコードを書いてもらいました。
tokusakurai は torisasami と D に取り組み、気がついたら通していました*3。
torisasami は F に行って、 tokusakurai には E の解法を聞いてもらいました。 すると tokusakurai が穴を発見してくれて解法を修正することができました。感謝。 最終的には解法は以下の通りです。
- 帰還可能な行/列の最初と最後をそれぞれ1と0にする*4。
- 帰還可能な行/列の残りの交差点は + と - の市松模様で埋める。
- 帰還可能な行/列それぞれについてできるだけ + が前に来るよう貪欲に埋めていく。ここで失敗するならこれは構築不能。
- 残りのマスは乱択する。
完全に証明した訳ではなかったですが、帰還可能な行/列だけを考えればこれで構築可能であること、残りも解空間が大きいので乱択で大体大丈夫であること、確実に構築不能なものははじけているのでコーナーケースがあっても恐らく個別に処理できることからこの解法で押し通しました。 結果的に特にコーナーケースもなく正解することができました*5。 順位表を確認するとかなり良い位置に付けていて安心しました。
F は tokusakurai と torisasami で相談して解法が見えているようだったので僕は G, H を見ていきました。 最近永続データ構造を勉強して H がその応用でできそうに見えたのでしばらく考えましたがよくわかりませんでした。
G も幾何だしよくわからないしで、F でバグが出ているようなので F のフォローに入りました。 愚直を書いてないみたいだったので、とりあえず僕が書いていったのですがバグを出してしまい苦しんでいる間に3ペナを出しながらも正解してしまいました。（悲しいね）
6完時点で残り10分くらいで、さすがに今からGHをやるのは厳しいのでお祈りタイムに突入しました。 順位表を見る限り6完は少ないものの5完はそこそこ出ており、自分のチームはペナを結構付けてしまったので心配でした。 コンテストが終了してドキドキで順位表をリロードすると6完のチームはほとんど増えておらず見事7位に入ったことが確認できました。（やったね） tonosama が全完していてびっくりしました。（すげー）
本番後
本番後は勝ったのでサイゼで豪遊しました*6。 サイゼリヤのメニューとしては高かったですがプロシュートがとてもおいしかったです。 デザートを食べ逃したのでまた行きたいです。 サイゼリヤといえば間違い探しですが最後の一個の間違いを結局見つけられることができず悔しかったです。
近くで東大でICPCに出た人々が何人も集まっているようだったので、サイゼリヤを出た後に合流しました。 最後に会ったのが約3年前の非競プロerの友達がいて驚きました。 他にもサークルの後輩が2人もいてびっくりしました。 noimi 君や SPJ、The Raspberry Candies、seguramu の皆さんと交流することができて楽しかったです。 ずっと競い合っていて、大学も同じなのに会うのが初めてなのは不思議な気分でした。
反省
個人的な心残りとしては最後1時間以上を何もできずに終っているところです。 Gの考察は後でじっくりやってみると（たぶん）できたのでこのあたりの選択を間違えたかなと思っています。
また、僕は他人と解法の相談するのが苦手で1人で突っ走りがちです。 今回も E で始めにちゃんと tokusakurai と解法の共有ができていればもっと速く E を正解できたのかなと思っています。 これから練習していきたいですね。
最後に
最後になりましたが、一緒にチームを組んでくれた2人、コーチを引き受けてくれた enjapma さん、教室の貸し出しの許可していただいた指導教官、審判団のみなさん、その他大会運営に関わるすべての方々には感謝を申し上げたいと思います。
時間が無くて参加記の執筆ができませんでしたが模擬国内の運営をしていただいたICPC OB/OG の会のみなさんにもこの場で感謝を申し上げたいと思います。
World Final を目指すのはかなり厳しい戦いになると思いますが、アジア大会に向けて精進していくので応援よろしくお願いします......！*7
