ICPC 2023 Asia Yokohama Regional 参加記

ICPC 2023 Asia Yokohama Regional にチームDELIAIRとして参加して8位でした！

大会前

対策としては，基本的に毎週 Universal Cup でチーム練習をしていました．あとは個人で精進をしていました．

実装で失敗した去年の反省から，実装の割り振りを工夫しました．実装が速くて正確なtokusakuraiが８割，torisasamiが1.5割，僕が0.5割程度を担当する形です．

大会１日目

チームのメンバーと一緒に会場近くのお店でラーメンを食べてから会場に向かいました．去年と同じ会場だったこともあり少し懐かしさを感じながら会場入りしました．

リハーサルでは，パソコンのセットアップ担当のtokusakuraiが真面目に話を聞いていなかったせいでCLionの立ち上げに苦戦していました．問題は去年と同じだったのでそれ以外は特に問題なくこなすことができました．余った時間はtokusakuraiがタイピングの練習をしていて僕はお菓子を食べることくらいしかすることがありませんでした．海外チームの問題を解くスピードが速かったので結構強いチームなのではないかという話をしていました．

チーム紹介ではtokusakuraiが英語を暗記しきていて偉かったです．

解散後は中華街で食事をしました． tokusakuraiが問題を解くフローについて提案してきました．僕が考察の大まかな指針を出して，torisasamiが詰めてtokusakuraiに伝えて，実装をすべてtokusakuraiに任せるというものです．僕はそれほどうまく行かないと思ったのですが，本番は実際に結構この通りに動くことになりました．

それからお風呂に入って，ABCの問題を軽く見てからホテルで11時過ぎに就寝しました．

午前1時くらいに目が覚めてしまって，午前4時くらいまで寝付けませんした．他の２人も途中で起きていたようですが午前2時以降はちゃんと寝ていたと思います．

大会2日目

コンテスト前

午前７時半くらいに起こされましたが，8時くらいまで布団から出られませんでした．

会場に近いホテルだったので会場には余裕で到着することができました．コンテスト前でしたがあまり緊張はしていませんでした．

コンテスト中

僕がA, torisasamiがBを見たあとに２人で残りを真ん中の方から手分けしてみていくことにしました．以下時系列です．

A: 問題文が読みやすく，DPをやるだけのようにみえました．始点が任意であることだけを丁寧に確認してGへ行きました．

G: ぱっと見よくわかりませんでした．少し考えて複雑なFPSとかだとお手上げだなと思いながら次へ行きました．

F: 少し考えるとすぐに性質が見えたので，解けたことを報告しておきました．

E: 制約からbitDPかと考えましたが特に考察は進みませんでした．

D: 構文解析かと期待したがそうではありませんでした．制約も小さいので区間DPを適当にやるだけだと考えて解けた報告をしました．

C: 数え上げ多いな〜と思いながら少し考えましたが，わりと難しそうに思いました．

M: torisasamiが読めてなかったので読みました．雑に三分探索、二分探索でいけるとおもいましたが，円の探索に手数がかかることを見逃していました．合流してきたtorisasamiと解法を詰め直して考察を終えました．途中でAをtokusakuraiに説明しました．

そのあとは，torisasamiと問題の概要や考察を共有しました． FやDをtokusakuraiに説明することもしました．

Dでペナが出てしまったのですが，これは2桁以上の整数を使えるとして問題を解いていたからでした．僕がBNFをよく見ていなかったことが原因だったので申し訳なかったです．

途中で順位表を見てEやG，Hが解かれているのを確認したのですが強いチームだけだったので信用できませんでした．

Eの $O(N^2 2^N)$ 解法をtorisasamiが思いついて更に $O(N 2^N)$ に落とせないか相談しました．詰まってGを見たところ，DPをしたときの状態がそれほど多くないことに気がつきました．

Eについては定数倍も軽いので $O(N^2 2^N)$ でも通るのではないかと主張しておいて，僕は他の問題を考えることにしました．最終的には $O(N 2^N)$ に落としたらしくて偉いです．

Hを考えたのですが特に進捗を生めなかったところ，tokusakuraiにEを説明したtorisasamiが燃やす埋めるを提案して一気に進みました．具体的なコスト関数を２人で計算して劣モジュラであることを確認したあと，詳細の詰めはtorisasamiに任せることにしました．

この時点で I, J は通されてたのですが J のほうがマシに見えたので J を考えていきました．合流したtorisasamiとパスグラフの場合を考えていると貪欲が思い浮かびました．木の場合に正当性の証明ができなかったのですが，反例の構築もできませんでした． HLD+遅延セグ木を使えば実装できることはすぐわかりました．実装が重いので他に方法がないかも考えましたが他に思いつきませんでした．そのまま重めの未証明解法を，Hを解き終えたtokusakuraiに投げることになりました．しかし２ペナが出てしまいこれは嘘解法ではないかということになりました．

そこから３人でIを考えていきました．行列で書いてみたり，双対を取ってみたりしたのですが全く解法が見えませんでした．詰まっていたのでJに戻ったところ正当性の証明ができた気がしました．そこで実装を確認したところ実装が間違っていたことがわかり，Jを正解することができました．

そのあとは Iを考えたのですがよく分からず，時間ギリギリでtorisasamiが適当な解法を実装し始めたので僕はCを考えてみました．結局 J は通すことはできませんでした．

Cはコンテスト終了後も考察をしてnが奇数のとき以外は方針が見えたのですがそこからがよくわかりませんでした．

コンテスト後

結果は８位でした． opt社から企業賞をいただきました．ありがとうございます．去年よりよい結果ではあるものの，SPJやThe Raspberry Candiesに負けてしまい悔しかったです．全体としてそこまで悪くはなかったと思うのですが，他のチームが強かったです．

Speed Star の4時間全完はさすがでした． WFに行くにはこのチームに勝たなければならなかったのですが，圧倒的実力の差を感じます．

Iは解法がとてもきれいで驚きました．２種類の液体を混ぜたときに作ることが可能な溶液の濃度と量をもっと丁寧に考えることができていれば解けたかもしれません．チームの中では自分が一番得意そうな解法なだけあって解けなかったことがとても悔しいです．

懇親会ではコミュ障なりに少し交流を広げられたので良かったです．

最後に

３年間チームを組んでくれたtokusakurai, torisasamiにはとても感謝しています．３人とも今年でICPCは引退になります．僕があまり実力を伸ばせなかったことは申し訳なかったですが，このチームで最後までICPCに挑戦することができてよかったです．

最後になりましたが，このような楽しい大会を開いてくださったICPCの事務局やスポンサーなど運営に関わった方々，懇親してくれた参加者の方々にはとても感謝しています。とても楽しかったですありがとうございました！！！！！

2023/11/29追記：本番で使っていたライブラリを公開しました。ご自由にお使いください。