ICPC 2023 Asia Yokohama Regional 参加記 (ruthen 視点)

ICPC 2023 Asia Yokohama Regional に pointN さん、niuez さん、ruthen で Big O of N cubed として参加しました。

メンバー

pointN
- 構築やインタラクティブなど天才ゲーを担当する。
niuez
- データ構造や木が得意。実装を担当することも多い。
ruthen
- 2 人に比べて明確な得意分野がないため~~お茶汲みをする~~ペアプロや考察を聞く側に回ることが多い。

本番前

国内予選までについては以下の記事を参照してください。

ICPC 2023 国内予選参加記 (ruthen 視点)

10 月中旬ごろから毎週末のどちらかに 5 時間のバーチャルコンテストを走っていました。

走ったセット（時系列順）

JAG夏合宿2019 Day1 (10/21)
JAG夏合宿2019 Day3 (10/29)
The 2nd Universal Cup. Stage 7: Two Capitals (11/4)
The 1st Universal Cup. Stage 11: Shanghai (11/12)
2020-2021 ICPC Asia - Taipei-Hsinchu Regional (11/18) ※ ruthen 欠席

ライブラリに関しては国内予選と同じものを使用し、その際に追加でいくつか印刷しておいた資料についてもそのまま持っていきました。

ホテルについては、横浜 DeNA ベイスターズファンフェスティバル 2023 の影響なのか予約がかなり埋まっていました。早めにとることをおすすめします。

Day 1

11 時に秋葉原駅に集合し、その後関内駅で降りて横浜中華街で昼食を食べました。その後 13 時半くらいに受付を済ませ、14 時から開会式→ルール説明→リハーサル→チーム紹介の順で進みました。

ルール説明では、英語を聞き取るのが大変だったので手元の資料を読んでいました。トイレに行くのにも申告が必要だったり、Day 2 ではコンテスト開始前に使わない荷物はすべて袋に入れることなど、ここで初めて知ったルールも結構ありました。

リハーサルでは、CLion の使い方や印刷の仕方やジャッジシステムの仕様を確認しました。想定よりジャッジシステムの性能が良くて TLE 想定のコードが AC してしまうことがありました。

チーム紹介は無難に真面目路線で行った方が良いです。（マイクの声が聞き取りにくく、ネタを考えてきても伝わらない可能性が高いです。）

その後夕食を再び横浜中華街で済ませ、ホテルにチェックインして解散となりました。 ABC が開始する前に寝ました。（起きた後に問題を確認しました。）

Day 2

コンテスト開始前

6 時くらいに起き、ホテルで朝食を済ませ、8 時過ぎにコーチや筑波大学のもう一つのチームであるGoodBye2023 のメンバーと合流しました。

会場に入るとお菓子が入った袋が置かれていましたが、それ以外は Day 1 と変わりませんでした。（具体的な時刻は覚えていませんが、お弁当も昼過ぎに配布されました。）特に遅延などはなくコンテストが始まりました。

コンテスト

※コンテストから数日が経過しているので一部の記憶が曖昧です。

国内予選では ruthen がセットアップと A を、pointN さんが B を、niuez さんが C 以降を読むことにしていましたが、今回は ruthen がセットアップを行い、niuez さんが A を、pointN さんが B やそれ以降を読むことにしました。これは問題文が封筒に入っており開始直後から A 問題を読めるため、また、セットアップが国内予選と比べてやや面倒であるためです。

セットアップが終わったら niuez さんが A を解けていたのでパソコンを渡し、AC。 B は pointN さんが読んでいましたがぱっと見わからないとのことだったので、niuez さんも B に参加し、ruthen は C 以降を読むことにします。

niuez さんが B は遅延セグメント木を使えば解けると言っていたので、実装を任せ、pointN さんと ruthen は問題に目を通していきます。

その頃順位表では F が通されていたので、pointN さんが読むと解法がわかり、内容を聞いて良さそうだったので B を通した niuez さんに F の解法を説明して実装してもらいます。F はすぐに通りました。

自分は CH あたりを読んでいましたが解けておらず、順位表を見ると DEK あたりが（たしか）解かれており、D は pointN さんが読んでいたので内容を聞きます。

区間 DP で行けそうとなり、 $O(N^4)$ かかりそうだなと思いつつ、 $N$ が小さめなので間に合うかもしれないということで niuez さんが実装を開始します。（当時 ruthen は反復回数が 1 桁であることを見落としていました。）

その間にだいたいすべての問題に目を通し終え、EGK あたりを中心に考えていきます。 D が通ると EG よりも K が解かれていたので、K を考えます。

インタラクティブ問題で、幅 199 おきにクエリを投げることによって大まかな位置を特定するところまでは良いですが、そのあと正確な位置を特定する際に三分探索などが必要になりそうでクエリ回数が足りない、みたいな話になります。最終的に pointN さんが幅 1 だけずらしてクエリを投げ、算数をすることで解く方針を考えたため、実装を任せます。

その後は（自分はあまり理解できていなかったのですが）G を考察していた niuez さんの話を聞いたり、E を考察していました。すると突然 E の BitDP 解が生えます。（この時は $O(M 2^N)$ でした。） niuez さんに相談したところ、 $O(N^2 2^N)$ に落ちたので実装を開始します。

E に提出しますが TLE で、コードを印刷して高速化について考えます。おそらくこの前後に K が通り、チームとしては E の高速化と G の解法を並行して考えます。 E については最終的に定数倍高速化手法をいくつか試したところ通りました。非想定だと思って $O(N 2^N)$ についてしばらく考えていたのですが、もうすこし早く試しても良かったと反省しています。

その後 G に取り組みます。自分は E に取り組んでいたこともあり解法を理解していなかったのですが、niuez さんが TLE すると言いつつコードが書きあがっていたので、提出してみることを提案し、ジャッジ結果を確認したところ WA が返ってきてしまいました。その後少ししてコンテストが終了しました。

コンテスト終了後

コンテスト後はスポンサー企業の紹介→問題の解説→ Yes/No の順で進みました。 Big O of N cubed は 6 完で 27 位でした。台湾勢のチーム数を踏まえると国内予選とほぼ同じ順位という感じですね。

pointN さんが $3^3$ 位だということに気づいており少し感動していました。 GoodBye2023 は 9 完して 9 位になっており、すごいな～と思いました。

懇親会では食事をいただき、いくつかの企業ブースも見に行きました。過去にインターンとして参加させていただいた企業も参加しており、（当時直接お世話になった方はいませんでしたが）挨拶もすることができて良いものとなりました。他にも何人か初めて話すことができた方がいたため非常に満足したものとなりました。会場で配られる名札には本名しか書かれていないため、ハンドルネームが書かれた名札を持参するのがおすすめです。

感想

B1 の秋に競技プログラミングをはじめ、ICPC のアジア大会には合計で 3 回出場することができました。うち 2 回はオンライン実施であったため、今回初めてのオンサイトは新鮮でとても楽しかったです。大会運営に関わってくださった全ての方々、そして、会場にはいなかった方も含めすべての競技プログラマの皆様、ありがとうございます。

私は現在 M1 で早生まれでもないため、これで ICPC は引退となります。競技プログラミングの活動としては一区切りつきますが、今後もコンテスト等には参加していこうと思っています。また、作問方面で協力できることは少ないかもしれませんが、JAG に入るなどして少しずつ競技プログラミング界隈に恩返し出来たら良いなと考えています。

これからもどうぞよろしくお願いいたします。