サムネイルはICPC Replayより。^[1]

概要

2025-07-04 16:30~19:30(JST) に行われた ICPC 2025 Yokohama 国内予選 にチーム「HAOU KAYAMA」として参加し、9問中8問を解いて全体14位を取りました。かなりの好成績ですが、ホスト校の+1枠にすら入らずに予選敗退らしいです。

全体14位でそんなことある？東京魔境大学になってしまった……

チーム

昨年のチームはRice_tawara459がAMATSUKAZEに引き抜かれて解散しました。
AMATSUKAZEの活躍についてはAMATSUKAZE視点の参加記shobon 視点,noya2視点を参照してください。

残ったNzt3とSotatsuがKoiKoiを引き入れ、新チームを結成しました。

ookayama を取り入れたチーム名にしたいということで「王 Kayama」とか「O-kayama」などの案を出し、強そうな覇王に決定しました。^[2]o3-kayamaとネタが被るのは聞いてないです。

チームメンバー

• Nzt3
  • 筆者
  • B3
  • AtCoder アルゴ黄
  • C++使い
• Sotatsu
  • B4
  • AtCoder アルゴ黄
  • AtCoderのIDがSotatsuではないので順位表にAtCoderアカウントを載せる拡張機能がうまく働かない
  • Python使い/C++も使える
• KoiKoi
  • B4
  • AtCoder ヒューリスティック橙
  • Python使い

チームの立ち位置

今シーズンの東工大(現 Science Tokyo)は黄色がかなり多く、実力の近いチームのボーダー付近での争いが予想されました。

暖色(Rating最高値2000以上)を2人以上含むチームは次の5つです。1人以上含むチームだともうちょっと増えます。

• AMATSUKAZE
• o3-kayama
• ACORN
• HAOU KAYAMA
• zer0shiki

国内予選の通過ルールは

• 全体10位以内なら通過
• 全体25位以内かつ学内3位以内なら通過
• 学内2位以内、学内1位以内ならさらに緩い全体順位条件

となっています。

今シーズンの東工大はホスト校ということでさらに次の追加枠があります。

• 通常選抜ルールで選抜されていない最上位の1チーム

これらのルールと東工大チーム群の実力を考えると、

• 学内3位以内なら通常枠で通過
• 学内4位なら追加枠で通過

という予想ができます。実際に去年・一昨年はそうなりました。

さて、暖色が2人以上いるチームは5チームありますね。鳩の巣原理より学内5位以下になるチームが1つ以上存在します。このチームは通過できるでしょうか？^[3]

準備

ライブラリ準備

昨年と同じく電子的準備が許可されていたので昨年準備したものにまともな整数幾何/小数幾何ライブラリを追加しておきました。練習で走ったJAG2017-Eをポンと通せるようにしました。

Pythonでのさまざまなデータ構造の実装も事前に準備しておきました。

練習

traPでの練習会とは別に、毎週CodeforcesのGymの3時間セットを走っていました。
Gymには難易度順セットはなく、セット選びが難しかったです。
国内予選に近そうだと思って走ったICPC Asia Taiwan Online Programming Contestは低難易度枠に大変興味深い問題が配置されており、序盤の練習になりませんでした。

Universal Cupのチームアカウントは作りましたが、予定が合わず3人揃ってコンテストに出たのは1回だけです。

環境整備

大学のPCに環境を準備するのが面倒だったので私のmacbookを使うことにしました。キーボード1台制限があったので普段使いの外付けUS配列のキーボードを封印してmacbookの配列で練習しました。

今年からコンテスト環境としてDOMjudgeが採用されているので、それに合わせてダウンロードしたサンプルを全実行するスクリプトも用意しました。^[4]

模擬国内予選

模擬国内予選のリハーサルってどういう役割なんですか？

爆速でABCD4完してEも通し、序盤の動きはかなり良かったです。
その後はFHに取り組んでいたのですが、どちらも通りませんでした。
Hで$y\equiv x(\mathrm{mod}{m}_1),y\equiv 0(\mathrm{mod}{m}_2)$ の式を立てた後に $y\equiv x{m}_2(\mathrm{mod}{m}_1{m}_2)$ だと思って実装していて頭が良くない。

結果は全体23位学内4位でした。あまり良いとは言えない結果です。

国内予選

potato167,simasimaによる実況配信があったらしいです。
https://youtu.be/8Ee8JIBq9yQ

以下問題ネタバレを含みます。

開始前

リハーサル問題をちょっと通したあとはカラータイル^[5] をやったり県庁所在地タイピング^[6] をさせたりお魚タイピングをさせたりして開始を待つ。

A

KoiKoiが担当。やるだけをやったらしい。
問題なく通る。(0:01)

B

Sotatsuが担当。問題文読解に手間取った。
問題なく通る。(0:06)

C

KoiKoi+Nzt3で式を確認してNzt3が実装。
同じ日が複数回与えられる←やめてね
問題なく通る。(0:10)

D

Cを通した時にはSotatsu+KoiKoiが考察を生やしていた。違う文字の境界の間隔の最小値を取ればいいらしい。
Sotatsuが基本の判定を実装している間にNzt3+KoiKoiでコーナーケースを探すと、めちゃくちゃある。
Nzt3がそれらに対応する方法を生やし、Sotatsuから実装を奪う。
途中で印刷問題文が届き、後半の問題の考察が動き出す。
実装でコーナーケース対応に失敗して1ペナを出すが、すぐに特定し修正して通す。(0:46)

F,E

Nzt3がDを実装していた間にEの木DP+貪欲方針が生えていた。
制約の割に計算量が小さすぎるけど正当ではありそうなのでSotatsuが実装。2ペナ。 (1:02くらい)
Eを印刷に回す。

Fの構築方法が生えていたのでKoiKoiが実装する。
Fが通る。(1:16)

SotatsuがEの木DP部分のバグを発見する。
差分のあるテストケースはすぐには生えなかったけど提出。
Eが通る。(1:22)

順位表を見ると全体順位は良いけど学内順位が低くてやばい。

確認時点では学内6位だったけどすぐに6完が増えて学内8位になったらしい。

配信で東工大の学内争いについて言及していたらしい。
https://youtu.be/8Ee8JIBq9yQ?t=2044

G

側面は三角形の場合と四角形の場合がある。それは辺が平行かどうかによって決まりそう。
でもこの位置に置いてあるからめちゃくちゃコーナーケースがありそう。
Sotatsuが生やした外角累積和での向きつき平行判定をNzt3が実装。サンプルが合ったので提出すると通る。(1:44)

コーナーケースはないの？

全体8位に浮上してそこそこ喜んでいた。

H

Nzt3がGを実装している間にSotatsu+KoiKoiが本質部分を生やしていた。
((,))に到達できるかが重要で、到達できないものは()交互列の長さを愚直に調べれば良いらしい。

Sotatsuが実装するが、サンプルが合わない。デバッグも難航。印刷に回す。
Nzt3が別の実装方針を生やし、実装を奪う。
Hが通る。(2:43)

I

同じ数が複数あってもペアにするべきものは一意に定まることがわかるのでとりあえず1~Nに番号を振り直す。

同じ番号が付いている要素の距離が全てNになれば条件達成で、1回の操作で高々2つの要素について距離を1変更できる。変更が必要な量から下界は考えられるが、サンプルでは下界が達成不可能な場合がある。

適当に交差を表しそうな項を追加するとサンプルが合う。
提出するとWrong Answerになる。(2:58)

時間をかければ解けるだろうけど時間がない。

終了後

学内5位で予選敗退らしいです。厳しい大学ですね。
解けるべき問題しかないと失敗が明確になってしまってつらいよ〜。

AMATSUKAZE,o3-kayama,ACORN,zer0shiki,Tsukuyom1 あたりに話しかけに行き、この難易度のセットは聞いてないという話をしました。
THSのブザービーターの話はここで知りました。

伝統となっている国内予選後カレー部をやったら学士1年生,社会人1年生^[7]を含む大勢が集まってすごいことになっていました。

おわり

今年のScience Tokyoは28チームが出場しました。
昨年より出場チームは減っていますが、簡単なセットだったので1チームの完数が増えたこともあり、合計150完と昨年の118完から大きく記録を伸ばしています。超巨大競プロ大学です。

B1,B2のチームが7完を決めていて来年以降にも期待が持てますが、私の引退までは追い抜かないで欲しいですね(最悪)。