The 2025 ICPC Asia Yokohama Regional Contest 参加記（AMATSUKAZE/noya2 視点）

The 2025 ICPC Asia Yokohama Regional Contest にチーム AMATSUKAZE として参加し、9 位（学内 1 位）でした。

チーム紹介

ICPC2025 に AMATSUKAZE というチームで出場しています。チームメンバーは以下の通りです。

noya2 （私）
- B4
- 幾何と典型が得意
shobonvip（shobonさん）
- M1
- 重実装と ad-hoc な考察が得意
Rice_tawara459（こめだわらさん）
- B4
- 数学と天才が得意

科学大の ICPC 事情

科学大からは次の 4 チームが出場します。

o3-kayama
AMATSUKAZE
zer0shiki
ACORN

Regional 級のコンテストの先には Playoff と Worldfinals があります。Regional 級のコンテストで優勝した場合は Worldfinals への参加が確定しますが、優勝しなかった場合は上位の成績を取ったチームが他の地区をいくつか集めた Playoff 級（日本からは Asia Pacific）のコンテストに参加し、その上位のチームが Worldfinals への参加権を追加で得ることになります。

ここで重要になるのは、Worldfinals に出場できるのは同大学から 1 チームまで、という制限です。つまり、Regional 級のコンテストで優勝したチームの出身大学の他のチームは、たとえ上位の成績を取ったとしても Playoff にすら参加できません。Yokohama に限って言えば、このコンテストで同大学の他のチームに優勝されたら困る、ということになります。

ものすごく強いチームでない限り、Regional 級のコンテストで優勝して Worldfinals への直通切符を得るのは現実的とは言い難く、まずは Playoff への出場権を得ることを目標にしています。そのため、Regional 級のコンテストでは、優勝とはいかなくとも上位に入ることを目指しています。実際には Playoff への出場にも同様の制限があり、Playoff に出場できるのは同大学から 3 チームまでです。つまり、科学大の中で最下位になることも避けなければなりません。

我々 AMATSUKAZE は他の地区のひとつである Seoul（韓国）の Regional 級のコンテストにも出場して、3 位の好成績を収めました。この成績を持って、Seoul から Playoff への進出がほぼ確定的となっていました。Playoff への出場が消える唯一のシナリオは科学大の他のチームに Yokohama で優勝されることで、これを阻止するための戦略がまず考えるべきことです。

先に挙げた科学大の 4 チームのうち AMATSUKAZE 以外のチームは他の Regional には出場しておらず、今回の Yokohama では

上位（13 位くらい？）の成績を取ること（科学大の中で最下位にならないこと）
科学大の他のチームに優勝されないこと

を目指しています。AMATSUKAZE としては前者は必要なく、後者のみ目指せば Playoff への出場権は得られます。とはいえ、後者を達成する他力本願ではない唯一の方法は自分のチームが優勝することで、これは前者を含むので、あまり関係ないという見方もあります。

そもそも科学大の 4 チームはどれもものすごく強いチームではなく、他の大学に優勝候補のチームが何チームもいるので、科学大のチームが優勝する可能性は低いと考えられています。

AMATSUKAZE の事情

先に述べた通り、Seoul で好成績を収めたため、Yokohama では優勝かそれ以外かにしか興味がないということになります（本当は優勝・科学大の他のチームが優勝・どちらでもない、ですが、科学大の他のチームが優勝することはないだろうと思っていたため）。

そのため、優勝確率最大化の戦略を取ることになります。いつもどおり取り組むことが最適戦略となるようなチームもいるかもしれませんが、我々は完数（解いた問題数）で勝負できるだろうと踏んで、初手で問題をすべて開いて得意な問題に張り付く戦略を取ることにしました。

コンテスト当日

ここからが参加記です。常体になります。

~0:00

直前の確認。問題は全部で 12 問ある。簡単な問題は PC が空いたら回収する。

~0:20

私が環境構築をする。shobon さんが ABCD を、私が EFGH を、こめだわらさんが IJKL を開いて読解する。D が簡単枠だったので shobon さんが実装して AC (0:20)。

~0:25

作戦会議？

shobon さん
- A：DP で可能だけど大変
- B：難しいが、得意寄り？
- C：貪欲そう、可能枠のはず
- D：AC 済み
私
- E：算数、簡単
- F：インタラクティブなので、こめだわらさんに投げる
- G：数学、FPS かも？
- H：WA が出る問題だけど、簡単枠
こめだわらさん
- I：ゲーム、謎だけど得意のはず
- J：パズル、たぶん解ける
- K：読解が不可能？
- L：見た目がやばい幾何、私が貰う

この時点で不可能枠は BFL だということになる。K はその後 shobon さんが普通に読解に成功して、できそうだけど難しそうとなり、高難度枠は CGIK ということになった。

~1:05

私しか簡単枠を持っていなさそうだったので、さっさとやっつける。H は辺ではない場所は $k$ 個連続できないので縦と横を識別可能で... $mod k$ で考えて... などと思っていたが、普通に左上から適切な順番で検出して消すことを繰り返せば良いことがわかる。実装も簡単、AC (0:45)。

E は有理数が出てくる変な算数だと思っていたが、有理数は表示を既約としなくて良いなら分母を $a, b, c$ のいずれかだと思って良くて、分子は二分探索すれば良い。制約が大きくてオーバーフローが心配になるが、積での判定を商での判定に置き換えるだけで良い。二分探索の上限を安全に設定するのに少し時間をかけたが、なんとか AC (1:05)。

この時点で 1 位は 5 完しており、圧倒的に速度差で負けている。よほどのことがない限り完数差をつけるしかないだろう。こめだわらさんが得意そうな F と私が得意な L があるので、希望はある。

~2:12

こめだわらさんが J が解けたようで、書き始める。WA が出る。私は shobon さんから C のヘルプを求められて一緒に考察しており、 $(1, 2, 1, 2, 1)$ を $2$ 手で達成できることに頭を抱える。最小値の回数まではこういう disjoint な区間 $2$ つを同時に消せる、のような雑な考察をしては、すぐに反例を挙げて却下された。とりあえず自分だけで考えてみることにすると、区間 add → 差分を見るの典型が普通に効くことに気づく。ただし、円環なので差分の総和だけでなく最小値（全体 add を固定する量）が必要。このもとで、 $+ 1, - 1$ を同時に消すことになるが、 $- 1, + 1$ の順番で消すと嬉しそうということになる。shobon さんに実装を託す。

こめだわらさんが長い睨み合いの末 J のミスを発見したらしく、AC (2:02)。実装を終えた shobon さんから、最小値を先頭に持ってくる必要があるという指摘があり、今のままでは変なケースで落ちるらしい。修正を加えると良さそうだったので出してもらうと AC (2:12)。強いチームでもペナルティを出しているようだったので、ノーペナは偉い。

~3:52

詳しい時系列は覚えていない。こめだわらさんが I に 2 回 WA を出して参ってしまっていた。A は shobon さんが大変な DP を書いてランダムケースを回すと TL に全然間に合っておらず、枝刈りも十分には効かないようで、沼にはまっていた。私は GL の考察をふわっと終わらせて、G は FPS をこねこねすれば解けそうということになる。shobon さんが A の改善を思いついて PC を占有している間、私は G の細かい立式を紙面で詰めて、実装の準備をする。A は時間計測で十分な速度が出ていそうだったので出すと AC (3:29)。ここまで自分の問題を自分だけの力で通すということがだいたい上手くいっていて良いが、速度は全然出ていないので、もう少し協力しあうべきなのかもしれない。

G の実装に取りかかる。実装はすぐ終わるが、紙面で詰めた式がなんと間違っているので、全然あわない。間違いを発見するも、実装待ちはないのでそのまま PC を占有する。これが良くなかった。紙面が間違っているのなら、紙面で詰め直すべきだった。PC 上でいろいろ直しながら全然あわない時間を過ごしてしまい、反省。 $max - 1$ が $max$ の右に存在しないという状態を数える際に、 $max - 1$ を固定していることを忘れて上限の $m$ まで総和を取ってしまい、簡潔に書けると思った式がもっと複雑になることに気づかず、PC 上で複雑な式を触ってしまった。加えて階乗前計算の長さを $1 0^{6}$ 程度に設定して RE も出してしまった。 $(a a + b)$ のような式を計算するので制約の $2$ 倍は必要だった。幸いそのミスにはすぐに気づけて、修正して AC (3:52)。

~4:11

とりあえず I を通さないといけない。こめだわらさんは WA の原因が分からずお手上げ状態らしいので shobon さんに愚直を書いてもらうことにしたらしい。こめだわらさんは、この問題のランテスを書けないと思っていたらしく、shobon さんが流石にそんなわけないと言って愚直を書く。自分は炎上中の問題には首を突っこみたくないので、通ると信じて L の考察を進める。

ランテスを書くとすぐに間違っているケースが見つかる。コーナーケースだったらしい。なんだか気になってしまい、結局 PC を見守ってしまったような気がする。直して提出するも、なんと WA 。ランテスに通るのに落ちるのはなかなかに変なので、異変をみんなで探す。結果としてランテスを $N \geq 2$ で回していたのがダメで、制約は $N \geq 1$ でなんと $N = 1$ がさらなるコーナーケースとなっていた。修正してやっと AC (4:11)。

~5:00

この時点で優勝はほぼ絶望的。少なくともここから 2 完しないといけない。本来ならこめだわらさんに 3 時間時点くらいで F の考察に取りかかっていてもらう予定だったし、自分も L をもっと早い段階で片づけておきたかった。とりあえず L はできそうなので、実装は詰められていないが PC が空いてしまったので、必要な部分だけでも書いておく。30 分くらいしかなかったが、実装は簡単なはずと思ってがちゃがちゃ実装する。が、これは悪い癖で、もっと詰めてから実装したほうが勝率が高いはず。二直線の交点を shobon さんに出してもらうなどして助けてもらいながら、とりあえず書き終えるが、なにもかも合わない。

まず整数で判定する部分が壊れているので、おかしい。まず考察に抜けがある（内接線の角度が外接線の角度以下であることはありえない）ことを発見したので、修正する。判定は合うようになるが、答えのスケールが致命的に違う。勘違いもしていたことが発覚する。直線の与えられ方は方向ベクトルの角度ではなくて法線ベクトルの角度だった。入力を改変して直したことにするもまだ違う。そうこうしているうちに時間切れになる。終了後、入力を変更すると今度は直線の式が違うということになり、頭が回っていなかったことが良く分かる。

全然順位表を見れていなかったが、科学大のチームを探してみると、科学大内で 1 位であることは確定していた。それにしても、科学大全体で調子は良くなかったように見える。

常体おわり。

yesno

優勝を狙っていた AMATSUKAZE としては何も面白くない、順位表解凍の時間です。観戦者視点での優勝の可能性すら残せなかったのは、完全に失敗でした。Playoff への出場も確定していたので、ドキドキもありません。ただただ、順当に強いチームが優勝することが明白です。実力通りにいったということですかね。

企業賞もなく、国内 8 位は国内予選と変わらず、本当につまらない感じになってしまいました。優勝はなんと 9 完止まりで、このセットで 10 完なら全然可能なのでは？という気持ちにさせられたのが余計に残念でした（我々は 8 完しかしていないので、完全に負け犬の遠吠えというやつですが）。

他の科学大のチームの成績としては、ACORN は凍結後に 1 問も通らず 29 位で突破ならず、という感じでしたが、o3-kayama と zer0shiki はそれぞれ 10 位と 13 位でなんとか Playoff に通過していそうです。

おわりに

AMATSUKAZE としては Regional 級のコンテストは突破したということになり、Playoff に進むことになります。他にも o3-kayama と zer0shiki も進むことになりそうです。次の舞台は桃園（台湾）で、来年の 3 月上旬の開催が予定されています。Worldfinals への出場を賭けた戦いはそこが最後で、科学大の中でたった 1 枠を争うことになります。ぜひご注目ください！そして、AMATSUKAZE の応援をよろしくお願いします！