2/29 ~ 3/3にベトナムのハノイで開催されたThe 2024 ICPC Asia Pacific ChampionshipにAMATSUKAZEというチームで参加し、65チーム中18位でした。

メンバー

• ebi_fly
  筆者。M1でラストイヤー。海外経験は小学生のときのみ。
• shobonvip
  B3。フロー担当大臣。海外経験は無限。
• noya2
  B2。構築、パズル、幾何が強い。海外経験なし。

事前準備

横浜の時から変わらず、UCupへの参加をしていました。

コンテスト直前

8時にホテルから会場へのバスが出ました。ベトナムの交通状況はカオスなので、絶対開催時間の9時には間に合わずこどふぉると思っていたら案の定30分こどふぉりました。
会場に入り、ぼけ～としていると、10分早まりました。9時20分にコンテストが開始しました。

コンテスト

序盤

PCにログインし、プリンタを使うためのものにログインしました。その後DOMJにアクセスしようとすると、エラーが出ていたので嫌な気持ちになり、スタッフに聞いたところ、「OKOK」と言われたので、全員ログインできていないんだろうなと理解しました。テンプレートを書いていたら、10分後くらいに会場の空気が変わったので、ログインしてみると、ログインできました。

中盤

shobinくんとnoya2くんが問題をざっと見てくれていて、自分の担当の問題が割り振られていたのでそれを読みました。Hが通されていたので、Hを読み、場合分けを頑張ればできるとわかったので、書くと通りました。（0:25）

shobonくんがJ解けたと主張するので、書いてもらいました。それなりにバグらせていましたが、通りました。（0:54）

自分はCを読み、よくわかんねえな～となっていると、苦しそうなnoya2くんが居たので、Cを投げ、自分はニコニコで木クエリのKを読みました。 $(x,lca(x,y),y)$ の辞書順であることがわかり、 $x=\lfloor \frac{k}{n}\rfloor$ であり、 $lca$ を固定したときの要素の個数もわかるので、セグ木の二分探索で $lca$ の頂点が求められることがわかりました。後は $y$ ですが、適当にやればできるだろ（え？）と思ったので解けたと主張しました。

shobonくんから、「Gが通されているが、ペアを $1$ つ見つけるのは鳩ノ巣原理でできるけど $b$ 最小のときができない」と言われました。読むと、クエリごとに見て行くのではなく、人毎に見ると $b$ 最小の人がわかるので $a$ を愚直に求めればよくないかと言いました。 $table[i][j]$ を $(i,j)$ のクエリの回答が一致した回数とすると、インクリメントの回数が $\frac{n(n+1)k}{2}$ すると少なくとも $1$ ペアは $k$ 個クエリの回答が一致しているので $1$ ペア見つけたとき打ち切ると計算量も大丈夫です。shobonくんから「それでいけます」と言われたので、Cでランダムチェッカーを書いているnoya2くんに交代してくれと言い、書くと通りました。（1:49）

その後、Cのランダムチェッカーをパスしたので出してもらうと通りました。（1:58）

Eでshobonくんが破滅していたので、コードを印刷すると、まったく印刷物が届きません。スタッフに聞くと、確認してくると言われました。その回答が返ってくることはなかったです。プリンターが別の場所から運ばれていて、プリンターが壊れたんじゃないかと類推しました。30分くらいしたら、DOMJのclarでプリンターが壊れていて今までのリクエストが消えていることが書かれました。

自分はKに戻って、 $y$ の求め方を考えましたが、よくわかりませんでした。noya2くんに相談したところ、並列二分探索でできる言われたので考えると、平衡二分木のマージテクでできることがわかりました。

noya2くんから、「Fは $k$ を決め打つと $O(N)$ で愚直に全部知べれる」と言われ、確かにとなりました。 $k$ の候補が、 $N$ の約数しかないのでワンチャン間に合うかもねくらいに思いました。その間にshobonくんがEを通してくれました。（3:01）

noya2くんが約数をすべて試すものを実装すると、TLEっぽかったので頭を抱えました。noya2くんが、素因数で割ったもののみ試せばよいと主張したので書いてもらい、TLE解と答えが一致しているか試してもらいました。答えが一致しないと焦りましたが、実行時乱数を使っていて、一致しないのはそれはそうになりました。紆余曲折ありましたが、通りました。（3:07）

終盤

ついにKの実装に取り掛かりました。 $x$ の値と $lca$ の値を求める部分まで書き、noya2くんにpbdsの使い方をレクチャーしてもらいましたがord_of_key関数がなくて困りました。Binary Trieで代用して書き始めました。

二分探索の判定関数や境界条件で頭を破壊していたが、残り20分くらいでサンプルが合い、投げるとREが出ました。苦しい気持ちになり、オーバーフローの確認や配列外参照の確認をしたが正しそうで、コードのどこを見ても合っていたので頭を抱えていたらコンテストが終わりました。

コンテスト後

tonosamaやBocchi The Techと話をして、tonosamaはWF通ってそうということがわかりました。AMATSUKAZEのペナが少なかったので、途中まで接戦で、WFの夢は見れました。

ミュージアムへの観光が予定されていたが、無くなり、よくわからない池で降ろされて閉会式会場まで自力であるく羽目になりました。交通量がバカで、かなり危険でした。

Yes/Noが終わり、正式にtonosamaが銀メダル・WF確定していました。おめでとうございます！

感想

これで自分のICPC選手編は終わりです。ラストイヤーで横浜初参加や、playoffへ行くなど貴重な経験ができました。知り合いも増えて、楽しいICPC選手生活でした。ありがとうございます。またオンサイトなどで会ったらよろしくお願いします。

来年度は、新生AMATSUKAZE（チーム名がどうなるかは知りません）が躍進してくれるのを期待しています。

最後に、ICPC運営・現地スタッフの方々、ジャッジの方々、選手の方々、コーチ、関わっているすべての方々ありがとうございました。