The 2024 ICPC Asia Pacific Championship 参加記（noya2視点）

こんにちは、B2の noya2 です。アルゴリズム班作問部の部長をしています。

2/29~3/3 の期間でベトナムのハノイで開催された The 2024 ICPC Asia Pacific Championship というプログラミングコンテストに AMATSUKAZE というチームで参加しました。

結果としては 65 チーム中 18 位という成績で、日本チーム内では 12 チーム中 5 位となりました。

海外での開催ということで、個人的には初めて日本の外に出ることになりました。海外遠征に関しては生きて帰ることを目標にしていたので、特に問題なかったと言えます（生きて帰ったので）。

コンテストの目標としては、一年生チームのBocchi The Tech に勝つことでしたが、それは達成できたのでよかったです。しかし、コンテストの内容としては後悔の残る結果になりました。しかし成果もしかっり得たという感覚があり、全体的には満足 $- ε$ といったところです。

この参加記ではコンテスト以外の内容にはあまり触れないつもりです。

大会について

この大会は今年度から新しく導入されたプレーオフ制度のひとつで、地区大会（日本なら横浜大会）と世界大会の間に位置するものです。地区大会で優勝したチームは世界大会への出場切符を手にし、それ以外の上位チームは世界大会への出場を賭けてプレーオフに招待されます。

東京工業大学からは tonosama, AMATSUKAZE, Bocchi The Tech の 3 チームが出場しました。日本からは世界大会への進出を賭けて合わせて 11 チームが出場することになりました（これに加えて、地区大会で優勝した東京大学のチームが招待されました）。

チームメンバー

メンバーと学年、および得意分野（担当分野）は次のとおり。

ebi_fly
- M1で年齢制限のため、ラストイヤー
- 木、DP、構文解析
shobonvip
- B3
- フロー、DP、数学
noya2(筆者)
- B2
- 幾何、パズル、ギャグ

割と得意分野が散っていて、個人の実力も同じくらいなので、バランスの良いチームだと思っています。

コンテスト

ebi さんに環境構築をしてもらう間、shobon さんと noya2 ですべての問題に雑に目を通し、誰が最初に着手するかを決める、という初動で臨みました。問題は $13$ 問あり、前半の $7$ 問を shobon さんに任せ、後半の　 $6$ 問を noya2 が割り振りました。割り当ては次のようになりました。

ebi : C,F,H,K
shobon : E,G,J,L
noya2 : A,B,D,I,M

これをもとに問題をじっくり眺めていきます。

まずは M を見ます。問題文に書かれたイラストからパズル系だと思っていましたが、全然違って、FPSゲーでした。実行制限時間が長すぎるので、ちょっと考察してすぐに撤退しました。

次に I を見ます。明らかに幾何なので自分が自分で割り振った問題です。まずは不可能枠ではなさそうなことを確かめます。考察を進めると、面積を最小化することから、与えられた点の多くが凸包の頂点になることがわかります。点対称で移り合う辺について、どちらかの端点は必ず与えられた点となる、のような考察をしますが、いまいち先に進めません。また、解けたとしても実装がそこそこ重そうなので、一旦飛ばします。

A を見ます。文字列操作の問題ですが、文字列長が短くて怪しいです。問題文自体はかなり簡単に読めましたが、どうもつかめません。ポテンシャルの考察をしたり、実はこうすれば常にできる的なギャグを疑ったりしましたが、順位表ではまだ解かれていないので一旦飛ばします。

D を見ます。これまた実行時間制限が長く、見た目をシンプルでヤバい匂いのする $mod 998244353$ です。とりあえず縦を $mod 6$ 、横を $mod 7$ で分類して、 $42$ 種類のマスを独立に考えます。ひとつずらした時の変化に注目すると、 $1$ つの種類が縦縞か横縞の模様になることがわかります。ここから先に進むには、独立に考えるのをやめて全体の整合性を合わせなければなりません。少し考えて何も出てこなかったのと順位表ではまだ解かれていないので一旦飛ばします。

ここまでで $1$ 時間くらいです。全部解けなさそうで辛いです。

B を見ます。と思ったのですが、ここまで全然解けそうな問題がなくて涙、という感じで、逆に ebi さんと　　shobon さんの問題はそこそこ解けていそうだったし、いくらかはACがすでに出ていたので、ややプレッシャーでした。そこで、 ebi さんの担当問題の C 問題をもらい、考察しました。順位表を見るとそこそこACが出ており、流石に可能枠だと確信します。

popcount の増減を考えます。 $x \to x + 1$ では m=count_rone(x) として popcount が　 $- m + 1$ だけ増加します。差分の情報が $N - 1$ 個と、どれか $1$ つの値の popcount の情報を合わせて必要十分にできるので、ここまでは順調です。さて、問題は最小化するパートで、それ以外にも $+ 1$ ずつしたものの popcount であることを利用しないといけません。ここで空からエスパーが降ってきました。 $m$ の値が最も大きいものは、最も多くの、かつ厳しい情報を持っています。そこで、その部分を貪欲に最小化すれば良いのでは？というものです。このことの正当性は、popcount 列の任意の連続部分列には最大値が複数現れないということから保証されます。そこで、この貪欲法に従って解を構築し、実際に条件を全て満たしているかを調べるコードを書きました。ペナルティをつけたくなかったので、念の為に愚直解と比較するランダムチェックを回し、問題ないことを確認して提出しました。無事ACです。時間がかかりすぎで良くないね。

ここまでで $2$ 時間くらいです。同じ東工大の激強チーム tonosama にペナ差で勝っていて、少し笑顔を取り戻します。

次に、ebi さんから F 問題をもらいます。問題概要を聞き、すぐに愚直でいけないか？となります。ひとつの $k$ に対して　 $Θ (N lo g N)$ 時間程度で、定数倍がやや重めです。約数の個数は $200$ 個くらいが最大で、実行制限時間に間に合わない気がしますが、とりあえず書いてみることにします。難なく書き終え、サンプルを合わせ、いざ最大ケースを回してみると、 $20$ 秒くらいかかりました。絶望的です。何かひと工夫入れないといけません。雑に頭を回していると、ふと、 $max / min$ はグループのマージによって小さくなる方向に行く、という考察が浮かびます。このことは、 $k$ として $N$ の約数ではなくて $N$ の素因数のみを確かめれば良いことを意味します。素因数は高々 $7$ 種類なのでかなり望みがあります。

さて、ここからの動きがかなり悪いです。全部調べて得た解と、一部調べて得た解を比較しますが、当然同じ値を出力して欲しいです。しかし、全然違う値を出力してきます。困りました。素因数だけで良いという考察に自信がなくなり、一度PCを離れて手で証明をしてみると、絶対正しいと思い直しました。再びPCにつき、コードをこねこねしていると、自分がかなり頭が悪いことがわかりました。検証に使っていたテストケースを実行時乱数で生成していました。つまり、同じケースで出力を比較しているつもりが、全然違うケースで比較していました。MAXBAKA of the year です。まともな乱数を使い、出力が一致することを確かめ、提出を行います。この一悶着に $30$ 分くらい吸われたのではないでしょうか。ともあれACを得たので、反省を後回しにして次の問題に取り組みます。

ここまでで $3$ 時間くらいです。ACの少し前に shobon さんのE問題もACが出ており、まだペナ差で tonosama に勝っています。ここから　 $2$ 問程度通せば十分勝てるし、K問題は通る余地があったので、一層気合が入ります。

ここまでの間に、ebi さんからKの内容を聞いており、並列二分探索で「適当に」やればいいと言い放って完全に任せ切っていました。「適当に」の部分がかなり大変で、実装は難を極めていました。本当にすいません。それから、__gnu_pbds::tree を使えばいいと言っておきながら、細かい使い方（テンプレート引数）を覚えておらず、結局別の方法として Binary_Trie を提案する羽目になりました。一番良くないのは、この方針は $lo g$ が　 $3$ 　つもついて遅いかもしれないことを分かっていたのに、別の方針に頭を巡らせなかったことです。並列二分探索を行う利点は、一回の判定をどの順番で行っても良いところです。これを素直に捉えれば、値の昇順に判定を行えることに気づけるはずです。しかし、本番では深いところから見れば良いので、 set の k-th element とマージテク、という大変な方針に手を出してしまいました。

実装はこの手の問題の実装に慣れている ebi に任せて shobon さんと noya2 は B 問題の考察をしていました。集合の大きさはかなり小さいことを考察しましたが、決定打が出ません。後から聞いた話では enumerate triangle らしく、未履修で涙、という気持ちになりました。勉強不足です。

そうこう言っているうちに ebi さんの実装が終わりました。しかしエラーが出る、サンプルが合わないなどで、実装もかなり重かったのでデバッグは大変そうです。自分も印刷されたソースコードを見てバグを指摘する作業に入りますが、細かなバグを直しては別のバグが出たり、あるいは新たな実装が必要になったりして、うまく連携も取れないまま全員でこの問題の沼にはまっていきます。やばいですが、他に残っている問題も明らかにやばいため、身動き取れず、という状況でした。

順位表を見ても、この問題は通せるだろうし確実に通すべきということが分かるので、そのままデバッグを続けました。しかし、結局、サンプルが合っても提出したら RuntimeError が返ってくるなど、典型的な沼にはまってしまいました。最終的に抜け出すこともできず、そのままコンテスト終了です。結局後半 $2$ 時間くらいは何もできないままコンテストが終わってしまったことになります。悔しいです。

Yes/No

順位表は終了 $1$ 時間前に凍結されますが、それが解除されるイベント Yes/No の時間です。

我々のチームはK問題に提出していますが、通せていないので特に楽しみなことはありません。他のチーム、特に日本のチームの順位が気になるところです。

結果ははじめに書いたとおりです。順位表を眺めてみると、今回は $7$ 完セットだったという気がします。 K を通せなかったのが辛いです。しかし、ペナルティを $1$ つしか出しておらず、序盤はかなり調子が良かったので、　 $6$ 完チームの中ではかなり早く解いた方でした。そのおかげで、横浜大会では負けていた $3$ つのチームに今回は勝つことができました。

また、目標であった Bocchi The Tech に勝つことは達成できたので、そこは喜びました。

tonosama は $8$ 完　 $6$ 位で銀メダルを獲得し、世界大会への進出を決めていました。すごいです。しかしながら、tonosama より強いチームが（中国を除く！）アジアに $5$ チームもいると考えると、恐ろしいばかりです。（tonosama は序盤でつまづいており、本調子ではなかったようですが）

感想

あとから確認すると、自分がはじめに着手するとした問題は順位表凍結前に全体で合計で $1$ つしかACが出ていない、という惨状でした。端的に言えば、難しい方から　 $5$ 問が綺麗に自分の担当になってしまった、ということです。運が悪いですね。それでも、途中で切り替えて C,F を通せたのは良かったです。

帰国後、upsolve でDIKを通しました。特にDは自力で通せたので、悔しい気持ちでいっぱいです。

今後について

ebi さんが今年でラストイヤーなので、この大会を持ってAMATSUKAZEは解散となります。ebi さん、お疲れ様でした。そして、最年長メンバーとしてチームを引っ張ってくれてありがとうございました！

今後は自分が木の問題などの重実装を担当することになると思います。shobon さんとは来年も同じチームを組みたいと話していますが、どうなるでしょうか。来期のICPCが今から待ち遠しいですね。精進してもっと強くなります。よろしくお願いします。