ICPC2025 国内予選参加記（AMATSUKAZE/noya2視点）

ICPC2025 国内予選にチーム AMATSUKAZE として参加し、8 位（学内 2 位）で突破しました。

チーム紹介

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

noya2 （私）
- 筆者
- B4
- 幾何と典型が得意
shobonvip（shobonさん）
- 3 年連続で noya2 とともに AMATSUKAZE のメンバー
- M1
- 重実装と ad-hoc な考察が得意
Rice_tawara459（こめだわらさん）
- 昨年のチーム WADATSUMI のメンバー
- B4
- 数学と天才が得意

AMATSUKAZE としては 3 年目で、noya2 と shobonvip に加えて 1 年目は ebi_fly さん、2 年目は Hemimor さんに組んでもらいました。 3 年目は Rice_tawara459 さんです。

科学大の ICPC 事情

国内予選の突破条件は少し複雑です。科学大などの学内争いが激しい場合は、全体順位に加えて学内順位も重要になってきます。学内から全体で 25 位以内^[1]に 3 チーム以上入ることが想定される場合、次のことを考慮する必要があります。

全体で 10 位以内に入れば突破
入らなければ、学内 3 位以内に入れば突破

東大のようなさらに学内争いが激しい場合、具体的には学内から 10 位以内に 3 チーム以上入ることが想定される場合は、全体で 10 位までに入ることが突破条件になります。科学大はここ数年、 ICPC やる気あり人材がかなり豊富で、東大のように層が厚くなって学内争いも激化しています。

さらに複雑なことに、科学大はホスト校に選ばれており、通常の突破条件を満たさなかったチームのうち最も順位が高いチームが追加で突破します。つまり、仮に全体で 10 位以内を逃しても、逃した中で学内 1 位なら突破できるということです。科学大には全体 10 位以内を目指せるチームが少なくとも 5 チームいます：

ACORN
AMATSUKAZE
HAOU KAYAMA
o3-kayama
zer0shiki

しかし、それくらい強いチームは国内で少なくとも 13 チームほどいるので、何チームが全体で 10 位以内に入れるかが科学大としての注目ポイントになります。昨年は 3 チームが全体で 10 位以内に入るなど勢いを見せており、少なくとも 2 チーム、堅くいけば 3 チーム、うまくいけば 4 チームが入るかもしれない、という見立てになっています。

科学大からは全体で 25 位までに 3 チーム以上入ることが確実視されており、その仮定の下で科学大からの突破条件は次のようになります。

全体で 10 位以内に入ったチーム数が 2 または 3 のとき、学内 4 位までが突破
- ”25 位以内のルール”で 3 チーム突破し、4 チーム目が”ホスト枠”で突破する
全体で 10 位以内に入ったチーム数が 4 のとき、学内 5 位までが突破

科学大の有力チーム 5 つがすべて突破するためには、全体で 10 位以内に 4 チーム入ることが必要になります。

AMATSUKAZE の突破シナリオ

問題は全部で 9 問あります。昨年は 6 問正解が突破ラインでした。昨年の AMATSUKAZE は序盤の難関を素早く切り抜け、終始優位に進め、ほぼ焦ることなく突破を決めました。今回も序盤でペナルティをつけないように意識し、実力をしっかり発揮して 6 問をすばやく正解すれば、その後は焦りも消えて着実に難問に取り掛かることができて、追加で 1,2 問の正解も見えるだろう、と思っていました。

国内予選の問題は難しいのです。難問を解くか否かで勝負が決するものなのです。

実際に起こったこと

結果的には最後まで序盤でした（？）。最終問題まで素早く切り抜け、いかにペナルティをつけずに早く全問題に正解するかを競うものになっていました。そして、我々のチームはそれに気づくのが遅すぎました。結果的には本当に時間いっぱい使ってようやくの全問正解でした。応援してくださっていた方々を心配させ、いろいろな意味で注目されてしまいました。すいません。おはずかし。

国内予選当日

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

A 問題

shobon さんの担当、問題なく AC (0:01)。

B 問題

私の担当。実装はすぐだが、サンプルが合ったと思い込み提出しようとするも shobon さんに止められもう一度確認すると全然合ってない（おい！）。ans = t とするところを t = ans にしていた、なにこれ。直して AC (0:05)。

C 問題

こめだわらさんの担当。ややこしい、複雑、コーナーケースが心配、らしい。いろいろありながら AC (0:11)。

D 問題

shobon さんの担当。問題は単純だが、場合わけ方針が面倒な上に、コーナーケースもたくさんある。ここが最初の難関だと認識する。市松模様の幅を特定できれば判定ができること、特定できない場合でも 2x2 のマスの模様に注目すれば良いことなどを私と 2 人で確認。実装がバグって F に交代する。私はデバッグには参加せず E を見る。

F 問題

こめだわらさんの担当。何も聞いていないが解けたらしいので D に代わって実装してもらう。実装がすぐに終わるも、サンプルが合わないらしく、D と交代しながらデバッグ。

E 問題

私の担当。木の問題でワープが出てきた、自分の作問 ARC179-D を想起する。制約が 2 乗を主張しているのでDPなどを考えるが、突然、貪欲で良いのではないかと思い始める。それだと準線形になり怪しいが、貪欲の正当性が証明できてしまった。貪欲ならかなりギャグなので、実装を渋ってしまい、D と F を優先してもらう。

D 問題 2

shobon さんがさまざまなバグを直し AC (0:45)。ペナルティをつけなかったのでかなり上手くいったと思ったが、上位を見るとそこまででもなかったかもしれない。それでもノーペナは気分が落ち着くので素晴らしい。

F 問題 2

サンプルが合っていないと思っていたら、実は合っていたらしい。そんな〜。まぁ仕方ない。AC (0:53)。

E 問題 2

私が不安になりながらギャグを実装する。実装はかなり簡単で、チームメイトに一応共有すると提出していいのではないか、ということになり提出すると AC (1:03) 。なにこれ。

一呼吸

ここまででそこまで悪くない動きだったので一安心する。とりあえず突破はしただろうと思い、GHIを見に行く。ここから先は担当はない。得意な問題を各々が取り組む。

G 問題

多面体の問題だったので、多面体が専門の shobon さんとこめだわらさんに投げる。自分はなんとなく辺が同時に何本平行になりますか？みたいな問題だと思ったが、制約が小さすぎる上に結果がギャグすぎて、流石にもっと複雑だろうと考え直す、G問題だし。

H 問題

面白そう。分割統治とか適当な 01 BFS などに思いを馳せるが、よくわからない。G の方針を shobon さんに話して、こめだわらさんに H に取り組んでもらう。

G 問題 2

shobon さんに角度の累積和の値の種類数の話をして、なんとなく合意をとり、shobon さんに実装してもらう。双方、中途半端に理解していたようで、実装が完了するもサンプルが合わない。その後お互い何か違和感を感じて考え直す。 $n - 2, m - 2$ の LCM をとったりしてデバッグを試みるが、頭は破壊されている。

私が辺の傾きなのだから内角ではなくて外角の累積和であることに気づき、shobon さんの実装を完全に無視して新しく実装し始める。実装は本当に簡単で、サンプルもすぐに合ってしまった。とりあえず提出すると AC (1:40)。なにこれ 2。

一呼吸 2

7 完したのに、順位がそこまで高くない。おかしい。順位表を見るとすでに全完（全問正解）が出ている。おかしすぎる。順位表のすぐ下には科学大のチームが並んでいる。ノーマークだった科学大のチーム Tsukuyom1 まで良い位置につけている。まずい。Hは少なくとも解く必要があり、最終的に全完を要求されるかもしれない、と怖くなった。前者は口にしたが、後者は呪いになると思って言わなかった。

H 問題 2

こめだわらさんが解けたと主張し、shobon さんと問答して、確かに解けていそうとなる。破滅実装にならないよう shobon さんと協力して実装を進めていった。重実装ではないとはじめは主張していたが、実装量はかなり嵩んでいた。

私はこのとき I 問題を考えていたが、値の重複を取り除けることぐらいしか考察できておらず、H を通すしかないと思っていた。自分は何も関われていないので祈るばかりだが、無限デバッグ編に入っており、明確な焦りを覚えた。

I 問題

今年の JOI 春の Day2-B のような雰囲気に似ていることを思い出す。円環をどこかで切り開いて、半分にわけて転倒数、みたいな雑な方針を思いつく。領域木で $lo g^{2}$ で、実装も定数倍も重い。そうは言うものの I もかなり通されており、早く実装を詰めて、取り掛からなければならない。

H 問題 3

なんとかバグが取れたらしい。提出するとなんと AC (2:18)。ありがとうこめだわらさん。安堵しようと思ったら、また順位表のすぐ下に科学大のチームが並んでいる。助けてくれ〜

すでに o3-kayama は全完していて、涙目。ここにはもう敵わないので、学内 2 位を目指す。

I 問題の明確な解法が浮かんでいない状況だが、まだ時間は残っている。全員で I 問題に取り組む。このときは全員焦っている。突破できないなんてことはないと思っていたから。

I 問題 2

簡単な方針に思いを巡らせるも、埒が明かないので、実装をし始める。一旦の雑なスケッチ程度の実装をするも、サンプルが合わない。順位表を横目に実装していたが、どこかのチームが何かの AC を出すたびに順位表が変動するのがチラチラ見え、気が散ってしょうがない。隠してもらった。

後ろの方で歓声が聞こえる、ACORN の喜ぶ声。順位表を見ると、なんと zer0shiki も ACORN も全完していた！これはまずすぎる。そもそも完数で負けるのは悔しすぎるので、なんとか我々も全完したい。ペナルティの差でまだ巻き返せる状況だが、I 問題の進行状況はかなり悪い。本当に助けて欲しい。

shobon さんは一旦自分の実装のデバッグの手伝いから離れ、もっと単純な解法がないかを考える。実はどこで円環を切り開いても答えが変わらないのではないか、というエスパーをもらって、流石にそんなことは...と思う気持ちと、問題設定的にはそれは十分あり得るという考えと、そうなら早く実装してしまった方がいいのでは？という気持ちと、今の解法を捨てて未証明の解法に走って後悔しないのか？という考えが巡ったが、一旦実装してもらうことにした。shobon さんを信じたというのが半分と、自信を無くして投げ出したのが半分。

多少バグらせたらしいが、修正するとサンプルが合う。もう 1 分ちょっとしか残っていない。祈りを込めて提出すると、なんと AC！（2:58）ありがとう shobon さん。

ペナルティの差で捲って、学内で 2 位につけた。学内 4 チームはすでに全完しているので、この中の順位が変わることはない。

残り時間

順位表で少し下にいた HAOU KAYAMA が I 問題を通さない限り学内 4 位であることが、実は最後に順位表を見た時点で分かっていたので、それを祈るか我々が I を通して突破を決めるかの 2 択だった。結局後者になったわけで、とりあえず突破を確信し安堵した。さらに嬉しいことに、我々が全完した時点では、なんと 10 位以内に科学大のチームが 4 つあって、これで HAOU KAYAMA を合わせて念願の 5 チーム突破がついに現実的になった。あと 1 分も残っていない、なんとか持ち堪えてほしい。

そう思っていた矢先、唯一の負け筋である京大のチーム THS が最終問題に提出し、AC してしまった。これで 10 位の ACORN が 11 位に転落し、10 位以内に入ったチームは 3 チームとなり、HAOU KAYAMA は突破ならずとなった。

そうこうしているうちに国内予選が終了した。まずは、昨年の国内予選で敗退したもののチームで練習を続けて今年突破を勝ち取った ACORN のところに行って喜びを分かち合った。

常態おわり。

おわりに

最後の最後で shobon さんに救われ、全問正解という結果で国内予選を終えました。例年通りなら全問正解は素晴らしいことなのですが、なんと今年は 12 チームも全問正解しており、いかに早く問題に正解するかを最後まで競うコンテストだったということになります。その中では我々は誤答を出していないだけ良いですが、速度としてはかなり遅めでした。後半の問題は難しいだろうという思い込みもありましたが、それ以上に冷静さを欠いていたのが反省点です。

終わってみれば、10 位以内に入ったチームは、はじめに予想していた面々とほぼ合致していました。このような事態は誰も予想しなかったと思いますが、東大・京大・科学大に至っては全完しないと突破できないという、かなり厳しい争いになりました。

次は地区大会です。国内予選を突破したチームは 12 月の上旬に行われる Yokohama Regional の地区大会に参加します。それまでまた練習を重ねます。応援よろしくお願いします。

正確には突破できなかった上位のチームを除く ↩︎