はじめに

こんにちは，B4 の noya2 です. ICPC2025 に AMATSUKAZE というチームで参加しています. チームメンバーは次のとおりです.

• noya2（筆者） : B4，幾何と文字列と典型が得意
• Rice_tawara459（こめだわらさん） : B4，算数と天才が得意
• shobonvip（shobon さん） : M1，重実装，発想，数学が得意

JAG 夏合宿 2025 このチームで参加しました. 合宿は 3 日かけて行われ，5 時間セットをあわせて 3 回走ります.

あとから分かったことですが，どのセットも A 問題から L 問題までの 12 問で，AB が簡単枠です.

Day 1

Day 1 は有志セットです. ABDEFGHJKL の 10 完で 1 位でした！

初動の環境構築は noya2 が行い，A 問題を shobon さんが，B 問題をこめだわらさんが見ます. 環境構築には多少時間がかかるので，ある程度できた段階で shobon さんの A 問題と交代します. すぐに通って全体 FA です！ B もすぐに通ります.

noya2 は FGH から見ていきます. F は問題がやや長いので飛ばします. G 問題は面白そうな見た目ですが，難しそう. H 問題は典型そうだけど，多分簡単ではなくて木だから実装も重そう，一旦飛ばします. G 問題の考察をします. ほぼ同じパスを選ぶことで局所的な flip ができることが分かり，自由度がかなり高そうな気がします. 一度の操作で $i+j$ ひとつに対して $1$ だけ flip するから，自明な上界を調べると答えになっていそうです. 実装は区間 flip 区間 sum ができればよく，遅延セグ木で処理できます. ふつうのセグ木では処理できそうにないことを 5 分ほどで確認し，少々面倒ですが遅延セグ木を写経します. L の FA が出ていましたが，こめだわらさんの進捗はなさそうだったので，PC を占有しちゃいましょう，G を FA します！

その間に L が Peoject Euler だということで shobon さんの手に渡っており，AC します. D も見ていた shobon さんはこれも簡単だと言っており，いくらか実装して通りました，これまた FA です！ 自分は F が簡単だと順位表が主張しているのでちゃんと考えると，偶奇だけ見て部分列を貪欲に取ればよいことになり，ぬるぬる実装して通ります. こめだわらさんは JK を見ています. J は天才構築，K は操作が意味不明らしいです.

shobon さんが H を解けたと言っているので聞くと，思ったより単純なハッシュですが実装は HLD+BIT を回避しないとまずそうです. Euler Tour でなんとかできることを知っていますが，詳細が出てこず，よくわからないまま shobon さんに書き始めてもらいました. 自分は E を見ます. 見た目がやばい三次元幾何ですが，かなり早く FA が出ていたので，可能ではあるはずです. 小さい方の領域に注目するのがいいのか，より位相的な性質に注目するのがいいのか，いまいち掴めませんでした. そうこうしているうちに H を書き終えたらしいですが，全然合わない，Euler Tour でパス和取得は LCA を経由する必要があることを忘れていました. 直してもらって通りました，これも FA です！ 木クエリは自分が実装しがちですが，今回は shobon さんがやってくれました，自分が素早く反応するべきでした. しばらく shobon さんと 2 人で CE を考察していると，shobon さんが E を解けたと言っています. 小さい方の領域の包含関係だけ見ればグラフの直径になりそうで，確かにそうだろうとなります. ただし，領域の隣接関係を見るには包含関係のうち最も厳しいだけ見る必要があります. 面積の昇順に見て，すでに誰かに包含されたものは包含する候補から消す，という方針を提案しました. 最も外側の領域にも注意する必要があります. また，包含関係を整数で判定する方法も伝えておきました. この時点では一般グラフではなくて木の直径になることには気づいていませんでしたが，計算量的に問題ないので，そのまま実装してもらって通りました. 幾何なのに自分が実装していません，反省しまくり.

こめだわらさんは K の操作の特徴付けをやめて J に取り組んでいたようです. とりあえず八進数だと思えば $75$ 頂点ならできて，そこから先は闇だそうです. PC が空いたタイミングで実験を書くようです. あまり上手くいかなそう？減らせはするらしいです. B を通して以降，ずっと苦しそうにしていたのですが，考察を共有してもらって，K と平行して考えます. shobon さんは K を考えています. 自分は問題文に stack と書いてあったので区間 DP とだけ言っておきました. J は謎です. スターグラフには限界がありそうなことを察して，いいグラフの形状を探していましたが，うまくいきません. shobon さんが K を解いたと主張しているので聞きにいきます. よく分かりませんが，素直な方針だと思うので，実装を詰めてもらいます. 自分が実装していなさすぎる. そうしていると，こめだわらさんが J の良い方針を思いついたようなので実装してもらいます. 自分は J のチェッカーを書いて，WA を未然に防ぐなどしました. J が通ってすごい，FA です！ 直後に順位表が凍結しました. K は shobon さんにとりあえず $O(n^5)$ を実装してもらいました. 自分は愚直を書いておきます. 最終的に $O(n^4)$ に高速化して通りました. すごすぎ〜！

自分も考察くらいしかしてないですが，shobon さんが強すぎて，こめだわらさんの unique AC もあって，ノーペナ 10 完で 1 位でした！完数差をつけたのも嬉しいです.

Day 2

Day 2 は JAG セットです. ABCHGJKL の 8 完で 5 位でした. 負け！

初動は Day 1 と同じです. A が難しかったようで，少し遅れましたが AB を通してもらいました. 自分は G が可能そうだったので取り組みます. priority queue でシミュレーションすればよいです，通りました FA です！ F も FA が出ていました. が天才そうなのでこめだわらさんに任せます. K は典型そうですが，うまい方針が一向に見えません. このセット難しすぎませんか. shobon さんが J を無限場合分けで解けたらしく，実装が大変そうですが，なんとか通りました，FA すごすぎ！

K は自然な再帰ができないかを shobon さんと検討していましたが，うまく計算量が抑えられないかもしれないということで，実装して検証します. 無理そう，そんな... shobon さんが別の方針を思いついたらしいので，自分は L に逃げます. Day 1 C と似ていますが，こちらの方はそのまま二部グラフの最大マッチングなので，最短増加路を考えるだけで良いはずです. 実は自分は最大流をソラで書いたことはなかったのですが，原理は知っていたので淡々と多始点 BFS + 経路復元をしさえすれば良さそうです. こめだわらさんが F の $\mathrm{mod}3$ 方針に辿り着き AC したあと，K も通り，その後 L も通りました.

こめだわらさんは D が原理的には解けると主張しており，重実装が得意な shobon さんが見ます. 自分は C の幾何をこめだわらさんと相談して，だいたいの解法を出してもらったのを聞きます. 多面体定理を華麗に用いており，かなり納得したつもりでしたが，凸包の境界上の点は頂点ではなくても必要であることに気づかないまま実装を始めてしまいました. こめだわらさんは初めから分かっていたらしく，共有が足りていませんでした. 反省. いずれにしろ合っていない実装で 2 ペナ，境界の点を含める処理でミスして 3 ペナもしました，悪すぎる. 合宿中初めてのペナをここで出してしまいました. なんとか AC です. その間 D ではこめだわらさんと shobon さんの間で解けた！→やっぱり解けてない！を繰り返していて，大変そうでした.

残り少ない時間で I を考えていましたが，実装が大変すぎる方針しか出ず，最後は D に専念することになりました. 結局面積の方が問題らしく，凸とは限らない単純多角形の面積を求める方法を知らなかったのもあって，全く貢献できませんでした. shobon さんが最後に思いついた方針でとりあえず実装してもらいましたが，考慮漏れがあって通りませんでした. 線分の XOR を取って外積で符号付き面積を計算すれば良いだけなのですが，どちらも発想になく，力不足を実感しました.

DaiMonge が強すぎました. それから科学大のチーム o3-kayama にも負けてしまいました，しかも完数差で. 悔しいです，Day 3 でリベンジします.

夜は懇親会と ABC がありました. ABC は F までかなり早く切り抜けられたのに G が解けなくてだめでした. min of mod of linear だと思っていたら想定は平方分割で，加える桁の個数が $9$ 個以下であることにすら気付いていませんでした. そもそも floor sum + 二分探索で良いことをその場で爆速で全完したポテロングさんに教えてもらいました. 勉強になります.

Day 3

Day 3 はなんと Dispersion さんの単独 W セットです. ABCDEFGHJK の 11 完で 4 位でした，勝ち寄りの負け！

初動から大変. A は難なく通りましたが，こめだわらさんは B で苦戦しているようです. 1 ペナが付きましたが，なんとか通してくれました. 幸先は悪い. H の FA が出ていたので見ます. $0$ を含められないことから左右の大小が入れ替わることはないので，できることはかなり限られています. 幅が変わらないこと，値が大きいことが長引きそうなことから，とりあえず右端の半分を選ぶことにすると通りました. J も 1 ペナで通ってました. K はこめだわらさんが通してくれました，見たことあるらしい？

自分は G を見ます. 幾何の見た目ですが，ABC で見たことがあるやつで，Li Chao Tree があればオフラインで処理できそうです. shobon さんに写経してもらいますが，一向にハッシュが合いません. サンプルはあったので致命的なミスはないと判断して提出すると WA が返ってきました. とりあえず配列外参照を直します，なぜ気付かなかった... しかしまた WA です. shobon さんはライブラリの写経ミスを疑っていて，自分の書いた部分の自信が満タンになったので，自分も写経のミスを探します. こめだわらさんには独立して得意そうな F を考えてもらっていて，解けたようです. 助かる. えーミスが見つからないのですが. と思ったらサイゼの間違い探しのボス問くらいの難易度のミスが隠れていました. bool mid = f(y, xs[(l + r) / 2] < f(data[index], xs[(l + r) / 2])); ど〜こだ？なんでこれのコンパイルが通ってサンプルも通るんだ，おかしすぎ. このミスを 79 行のライブラリの中から見つけたときは多少キていましたが，直して通りました. FA が惜しいところで取られて，激おこです. 平行して書いてもらっていた F も直後に通ります.

気持ちを切り替えていきます. ペナが嵩んでいるので，完数で捲りたいです. D が天才そうなのでこめだわらさんに投げて，自分は E を見ます. 最大化と最小化はマッチングと燃やす埋めるでいずれにしてもフローで解けそうです. フローは shobon さんの担当なので，相談して合意を取り，実装に移ってもらいました. 自分は C に行きます. 手で実験してみると，二部グラフの頂点の偶奇で答えが一致しており，しかも最適かそれ +1 が答えになりそうな予感がしてきました. 小さいグラフから $2$ 頂点ずつ接続して... のような証明が回らないか検討していましたが，うまくいきません. E が通って shobon さんに相談しながら考察を進めましたが，いまいち証明らしいものは出てきそうにありません. 一旦別の方針を考え，二部グラフの頂点の偶奇の個数に関する自明な不変量に注目すると，最適が可能であるための $\mathrm{mod}3$ の必要条件が出てきました. そこそこ綺麗で，サンプルも説明できるので，これが通るならギャグすぎるなぁと思いながら書く判断をしました. D が通っていてすごいです. C は実装は重くなく，何事もなく通りました.

IL が残りました. L は AC が出ていたので，こめだわらさんと shobon さんに取り組んでもらい，自分は I の幾何に行きます. 見た目がやばい問題でしたが，整数で処理できそうな綺麗な問題の予感がします. L が解けそうだと言われ，最終的に I に時間が残るだろうと思っていたので，自分は L には首を突っ込まないことにします. まず，凸包の境界に乗っている辺しか選べません. そのような辺であって向きが真逆のものがあれば Yes です. 他には直角二等辺三角形も Yes です. こめだわらさんの指摘で，二等辺三角形も Yes で，そこから直角三角形も Yes です. 条件が多すぎます. しかし，最終的に無限回操作するのだから，結局は向きが真逆のケースに帰着するだろうと思って，証明もできたつもりになっていました. 検証はしてなかったので，もしかしたら間違ってるかもと思いながら，信じてしまいたくなっていました，良くない. 2 ペナしながらなんやかんや L が通ったので，全員で I を考えます. 残り時間もあまりなく，とりあえず凸包を取って，境界上の辺を列挙する部分は必要だろうと思って実装を始めます. shobon さんは実は任意の三角形が Yes なのではないか？と言いますが，流石にそんなことはないと言い切ってしまいました. そんなことはあるのですが，結局向きが逆のケースと自明に不可能なケースを片付けて，他は Yes として提出して WA をもらいます. その後もよくわからないまま WA を重ねてコンテスト終了です. 最終的には「三角形なら Yes 」に近いことをしていたのですが，一応確かめておくかと思って書いたものは間違っていたので，やることはちゃんとやれという感じです.

o3-kayama には勝ちましたが，完数で捲るまではいきませんでした. I で任意の三角形でできることに，そうではないか？と訴えられても納得できなかったことが悔しいです.

交流

コンテスト外の移動や食事などの時間は同じ宿泊室のメンバーと過ごしました. とても楽しかったです. 特に自分が競プロを始めたきっかけのひとつであった京大の yuma220284 さんと同室で，ペンシルパズルのことや ICPC 事情などたくさんお話しさせていただきました. Day 2 の夜には話し足りない人々が談話室のそばで競プロのあれこれを喋っていました. ライブラリの話や EGOI2025 Day2 D の話をしました.

おわりに

すごい調子が良ければ勝てるが，そうでない場合はまずまず，といったところですかね. コンテストの感想を準備陣と共有する時間がもっと欲しかったですが，そもそも現地に来ている人が少なくて寂しいです. 代わりにこの参加記で伝われば嬉しいです. すいません，文字の密度が高すぎませんか？

横浜でみんなと戦うのが楽しみです. ありがとうございました！