ICPC2023国内予選 参加記

今年もICPCの予選に参加したので、参加記を書きます。

チーム情報

チーム名：Type-C
所属：千葉大学
メンバー：stoq, hiryu, WiIIiam

自分 (stoq) は 4 回目の参加、他 2 人は初参加です。
hiryu くんは B2、WiIIiam くんは B1 で、来年以降も ICPC に出てくれる若い人が欲しかったので最終的にこのメンバーとなりました。

余談ですが、"WiIIiam" の I は大文字の i です。

作戦

自分が一番コーディングが速く ICPC の提出方式にも慣れているのと、チームメイト 2 人は考察が強いことを考慮した結果、自分がコーディングを全て担当しその間に 2 人に解法を考えてもらう作戦にしました。
特に hiryu くんは AGC の銅 diff 構築を本番で通すほど考察が強いので、自分の苦手な構築が出た場合は丸投げするつもりでいました。
結果として、この作戦が功を奏しました。

当日までの練習、リハーサル

過去の予選 1 年分 (2019) と模擬国内で練習しました。
過去問の方は D で詰まってしまい 3 完でしたが、模擬国内は調子が良く 5 完でした。

リハーサルでは研究室のプリンターのドライバをインストールするなどして準備を整えました。

本番

問題文：
icpc.iisf.or.jp

初動は簡単な環境構築をしたのち、自分が A、WiIIiam くんが B、hiryu くんが C を開きました。

A はシンプルな実装問題でしたが、ペナルティを絶対出せないので丁寧にチェックしてから提出しました。
緊張していましたが、無事 AC(5:57)。

B 問題はあみだくじの問題で、WiIIiamくんに問題の解釈が合っているか確認しつつ実装。これも簡単な全探索の問題で、落ち着いてAC(16:29)。

C は構築の問題で、大昔の Div 1 で似た問題を見たことある気もしましたが思い出せず、hiryu くんに丸投げしました。
(後で調べたら見つけたものの、言うほど似ていなかった。Problem - B - Codeforces)

D を先に見ると、なんとなくいけそうな感じがしたので並行してこちらを考えます。
答えが最大になるのは かつ が全て 'o' のときですが、これは の 7 個で達成可能です。
よって 6 個以下の場合を全探索し、各場合についてナップサックDPをすれば解けそうです。
6 個以下の場合を DFS で実際に数えてみると 14 万程度だったため、この方針で書き進めます。

ナップサック DP パートは bitset を使うと速くなるな～と思いつつ使わなかったので実行に 2,3 分かかりましたが、提出すると無事 AC(50:47)。

D を解いている間に hiryu くんが C を閃いたようなので、解法を聞いて実装。左上から順に 1,2,... としたとき、奇数全て→偶数全て と並べると条件を満たすようです。
実装ではアサーションを合わせて書いたので実行が終わるなら AC が出る、と考えていました。無事実行が終わったので提出。

しかしここでトラブルが発生。
ファイルを提出した直後、WA でも AC でもなく「サーバーに接続できません」のような画面が出てしまいました。
そこでリロードボタンを押すと、Wrong Answer の画面が。解法に誤りがあると思い肩を落としましたが、Top 画面に戻ると何故か No.2 のデータセットが用意されていました。
どうやら変なタイミングでリロードしたせいで 2 回同じファイルを提出した扱いになってしまったようです。
動揺しつつも No.2, No.3 のデータセットで提出すると AC(1:09:52)。

この後コーチを通じて審判団にペナルティを取り消せないか聞きましたが、サーバー自体は正常だったようでダメでした。
(まあ結果的にはこのペナルティがあってもなくても順位は変わらなかったので、セーフ)

気を取り直して E に取り掛かります。
E は先に見ていた hiryu くんから、 を見て 個改ざんしたときの最後のペアの辞書順最大、とする DP で解けそうと言われ、実際それでいけそうだったのですぐに取り掛かりました。
はじめに x と y を swap することで通常の辞書順序にしておきます。

DP の遷移は、全てちゃんと書こうとすると細かい場合分けが必要になります。
しかし実際には、 から配る遷移について、

• 改ざん後(改ざんしない場合も含む)の としてあり得るのは の 3 通りのみ
• 改ざん後(改ざんしない場合も含む)の としてあり得るのは の 4 通りのみ

しかありません。そこでこれらの12通りの候補を全部調べて条件を満たすものだけ遷移する、という実装方針を取りました。
これはかなり定数倍が悪いですが、ICPC は手元実行のため、実装の軽さを優先しました。実行は 4,5 分かかりましたが、実装・デバッグにかかったであろう時間を考えれば十分プラスだと思います。提出して、AC(1:50:34)。

F は幾何でしたが、なんと WiIIiam くんが解けたかもしれないとのことで、hiryu くんも正しそうと言っており、解法を聞きました。
(strictな)凸包を取った後、凸包に含まれる全ての点 と前後 2 方向について、多角形での[次/前]の頂点を 、凸包での[次/前]の頂点を としたときに、 が直線 上にあることが必要十分、とのことです。

2人に都度質問して自分が解法を理解できているか確認しつつ、全力で幾何ライブラリを写経して実装。
デバッグを繰り返してサンプルが合ったので提出すると、なんと一発でAC(2:36:03)。
もし自分だけなら間違いなく思いついていなかったので、チームの強さを思い知りました。

ここら辺で順位表を見てすげ～と言って踊っていました。

G は期待値の問題で、式変形をこねくり回していると終了 3 分前にそれっぽい DP が降ってきましたが、時間切れ。

H は見ていません。

結果

301 チーム中 6 位で予選通過しました！

まさかここまでの高順位を取れると思ってはいなかったので、ただただ驚いています。

感想

チーム戦かつ手元実行という、ICPC ならではの環境をうまく活用して勝つことができたと思います。
実装担当であるため緊張していましたが、同じようなバグに嵌り続けることなく素早く実装できてホッとしました。
(余談ですが、次のようなテンプレがデバッグでかなり役に立ちました。普段から愛用しています)

#define dbg(x) cerr << #x <<  ":" << x << endl;

また、チームメイトの考察力にもとても驚かされました。
3 人いれば同じ問題を様々な視点から考えることができるので、それらをすり合わせて解法に辿り着くのが面白いです。
昔と比べるとコミュニケーション力が(主にゼミのおかげで)上がっていたので、齟齬なく意思疎通ができたのもいい点だったと思います。

アジア地区もこの調子で頑張ります！