ICPC 2024/25 Asia Yokohama Regional Contest 参加記（shobon 視点）

ICPC 2024 Asia Yokohama Regional に AMATSUKAZE で参加して 9 完 4 位でした！

目指していた優勝は叶わなかったものの（スクウォが強すぎた……）、playoff に進出できそうでよかったです。今回は day 2 のみ書こうと思います。もちろん（？）コンテスト内容のネタバレを含みますのでご注意ください。

チームメンバー

noya2 ... B3. 幾何・天才・パズル・数え上げが得意
shobonvip ... B4. ライブラリタイピング係。構文解析・フローをやる（得意とは言っていない）。ぬいぐるみなでなでが得意
Hemimor ... M2. 超難問を通す。特にProject Eulerっぽい数学が得意

この記事を見ている人はこの記事も見ています

この大会の目標

今回、Seoul Regional にも参加した（5位）だったので、ICPC の playoff 進出条件的にはほぼ確定でした。ただし、Yokohama Regional で他の東工大チームに優勝されてしまうと playoff にはいけないので、目標は「優勝 OR 東工大の他チームの優勝阻止」でした。

コンテスト

コンテストの説明が終わり、「今何時？」となっていたところでカウントダウンが表示されましたが、残り2分で開始で笑ってしまいました。心の準備ができてなさすぎる。その後、コンテストは始まりました。

noya さんが環境構築をするので、自分はまず A を見て Hemimor さんに B を見てもらいました（これはコンテスト前に決めていました）。

A は見ると値を座標圧縮し、各値について、 $A_{i} = x, A_{j} = x, i < k < j \Rightarrow A_{k} \neq = x$ で $i < k < j \Rightarrow A_{k} > x$ ならこの $2$ つは 1 回でまとめて操作した方がよい、ということがわかりました。最初は嘘解法を思いついていましたが、嘘解法を落とすコーナーケースはサンプルになかったです。

環境構築が終わったあと、Aを書いて通りました (0:08)。B にすぐに交代し、通りました (0:12). その後、自分は C と、D はやばそうなので飛ばして E を見ました。C は全域木をいい感じに取る問題ですが、結構不可能そうで逃げました。 E は構文解析っぽい見た目でしたが、考えてみると P からスタートして再帰で見ていくだけでよさそう（ただし見た頂点はメモする）ということが分かりました。そうでなくても問題が「計算せよ」なので簡単枠なのは間違いなさそうです。ただし E の詳細の問題文がよくわからないので読み込みます。結局わかりませんでしたがよさそうなので良いということにしました（？）。

Hemimor さんによる K の実装が始まっていましたが、 WA が出たらしいので交代してもらい E を書きます。 Clion の扱いに慣れてなくて、いきなりマルチカーソルが出たり再帰関数に全部波線が引かれたりして困りましたがなんとか書き切り通りました (0:43) その後、K のコーナーが見つかったそうなので書いてもらい、通りました (0:49)

その後は「8sec 問題文理解不可」とメモされている H の問題文と、簡単数学感がある F を読んでいたと思います。ただ noya さんから F はヤバいと言われ、少なくとも序盤に解く問題ではないという判断に。その後 I で segtree を使うらしいのでそれをタイピングしました（一発でハッシュが合いラッキー）。 I は noya さんが実装します。

C が通されていたので C を再考察。 Hemimor さんにも問題を共有し、貪欲だと思うという気持ちを伝えました。その後、各頂点について、Yokohama からの $q_{i}$ の和が最小になるように貪欲に辺を選べばよいのでは？と思い伝えましたが、考えている貪欲が Dijkstra 法のアルゴリズムと同じだったので最短距離として改めて眺めると、 Dijkstra で最短距離木ができ、「各頂点に最大限忖度をしても最短距離よりは効率的にならない」ということで、各頂点の寄与を理論上すべて最小にすることが判明。これは感動！これはすぐ書けるので、 I が通ったあとに C を書き、通りました (1:18)

その後、noya さんが 0-AC の D を書き始めます。自分は Hemimor さんから L 問題の内容を教えてもらい、 J を読みました。H, J, L のうち J を考察しはじめました。 LP っぽい形になりましたがなかなかいい感じに考察できず。各水溶液が無限にあれば 2 個の水溶液だけ選べばよさそうですが、水溶液の最大容量が決まっているのが難しい。フローも視野に考えましたが、結局わかりませんでした。 D は noya さんが通し、first accepted ですごいです！(1:42) ここで一瞬 1 位になったと思います。

その後、Hemimor さんが G を書きはじめました。自分は H, J, L の問題内容を noya さんに伝え、 J を少し考えたあと、 L を考え始めました。L は区間 DP っぽい制約（もしくはフロー）ですが難しい！　少なくとも各区間について「 $k$ 回操作で全部消せるか？」が分かればあとは DP すれば OK、という形になりました。その後、結構な時間をかけて「和に注目すれば全部消すのに最小で何回操作が必要かが分かる」ことがわかりました。これは一次合同式を解けばOKです。ほどなくして、「もし全部消せるなら、その最小操作回数が絶対に可能」ということがわかり、一気に正解に近づいた気がしました。その後、dp[i][j]を「 $[i, j)$ の区間の中で操作が $x$ 回可能」という条件を満たす $x$ の集合と定めると、部分和問題っぽくなり、BITSET を用いて更新すれば $O (N^{4} /384)$ で解けることがわかりました。しかし、 $N = 500$ なので noya さんに言うとやめたほうが良さそう、ということになりました。もうしばらく考察すると $x$ 回可能なら $x - 1$ 回も可能なので、 dp[i][j] は可能操作回数の最大値と定めればよい、ということに気づきました。これで $O (N^{3})$ が完成！

G が解けたあと、 L を書きました。すぐに実装が終わりましたが、提出して WA でした。（ここで凍結1時間前）やっぱり考察が間違っていたのか……？ともかく、 F の方は各頂点の距離の関数が書ければ三分探索でできそう、ということで noya さんと Hemimor さんが解けていたので F を書いてもらいます。その後、 L の実装ミスをなんとか見つけ出し、反例も出して直しましたが再度 WA。何度みても実装は合っているので考察ミスしかないということに。うーんうーんと唸りながら実装をまたまたよく眺めていると、 chmax(dp[i][i+len], max(dp[i][j], dp[j][i+len)) と書いてある箇所が正しくは max ではなく足し算（各区間の操作回数がマージされるので）になることが発覚。これは自分の調子が悪い。ただ反例が全然手で出ないので直したあとランダムケースを回しましたが、これもまた全然反例がでない。もしかして実は max でも問題なかったのか？それはそれとして F もバグっている様子です。 noya さんと Hemimor さんは F に全集中しています。

最後の悪あがきとして終了 3 分前に正しいと思っている L のコードを提出してみると、なんと Correct と表示されました。なぜ反例が出なかった？なにはともあれ嬉しかったです。ただ、 F は諦めたようです。そのままコンテスト終了。どうやら F は遷移が 2 個ほど足りなかったようです。

順位発表

同大学内1位は嬉しかったです！ただ、3位以内に入りたかったです。優勝するにはやや実力不足でした。

WADATSUMI、Bocchi the Tech はどちらも1桁順位ですごかったです。

反省

序盤は超よかったです。あと、 L で実装ミスをしなければよかった！ L のランダムケースの件は、終了間近だったのもあり、チームメンバーをランダムケース生成を諦めて出してみるか聞いたほうが良かったところも反省かもしれません。

勝因はもってきたぬいぐるみ（国内予選優勝に寄与）と競プロドリンクである ZONe （ZONe は AtCoder に ABC を開いたことがあるため、 ZONe は競プロの縁起がいいドリンクだと思っている。近所で 190 円で売られているため、そこで買った）

懇親会

おなかいっぱい食べました。他の人とたくさん交流しました。

おわりに

面白いコンテストをつくったスタッフのみなさんありがとうございます！このコンテストに参加できて本当に幸せです。playoff では他の東工大チームに勝てるようにたくさん精進します。