はじめに

8月31日から9月5日にかけてアゼルバイジャンのバクーで開催された ICPC World Finals に東京科学大学代表として参加しました。チームメイトは simasima と Ponjuice、コーチは tatyam さんです。

お詫び: 写真を撮る習慣が身についていないので、写真少なめです。

準備

チーム練習で過去の WF のセットを走ったりしました。

ライブラリを整備します。tatyam さんの ICPC_notebook に 自前ライブラリや kactl を突っ込んで 25 ページになるまで適当に削りました。

ライブラリをファイルに入れて持っていく必要があるようです。どんなファイルがいいか人々に聞いたところ tatyam さんが Z ファイルをお勧めしてくれたのでそれにしました。

Day 0 - 移動

バクーへは日本から直行便がないので、飛行機を乗り継いで行く必要があります。我々のチームはカタールのドーハを経由しました。

出発は夜でした。羽田空港に現地集合、simasima がスマホをタクシーに忘れたりしてて面白いです（笑い事では、ない）。
モスバーガーで夕食を食べた後、無事に出国できました。

羽田 - ドーハ便は、夜出発早朝着なのに機内食が2回出てびっくりしました。寝たり事前にダウンロードしておいたゲームの実況動画を見たりして過ごしました（YouTube Premium の学割プラン、ありがとう）。

ドーハ空港で 5 時間ほどの乗り継ぎです。カタール航空のハブ空港で、めちゃくちゃデカいし冷房がガンガンに効いていて少し寒かったです。

ドーハ - バクー便は、席が 3+1 で私が 1 だったのですが、隣に誰も来なくて快適でした。機内食を持ってきた CA の英語が聞き取れず敗北...

Day 1 - Registration

昼過ぎに空港に着き、アライバルビザを取って無事入国できました。日本人はなぜかアライバルビザが無料です。
あとはゴロゴロして夕食を食べて Registration に行ってこの日は終わりです。Registration では、ライブラリなどコンテスト会場に持ち込みたいものを預けたり、写真を撮ったりします。

Day 2 - 開会式

よく眠れました。朝食を摂って、Baku Convention Center にバスで移動します。
この日は Alumni Talk とエクスカーションと開会式がありました。

Alumni Talk は負辺アリ単一始点最短経路問題の話で、結構複雑であまり理解できませんでした。これらしいです。

エクスカーションは、Baku Convention Center の隣にある Heydar Aliyev Center です。絨毯があったりアゼルバイジャンの歴史が紹介されていたり謎美術品がたくさんあったりしました。建物の形が面白い。

開会式も Heydar Aliyev Center のホールでした。国歌が流れたりスポンサーや参加者が紹介されたりダンスや演奏があったりしました。

Day 3 - Dress Rehearsal

腰が痛い。今日も Baku Convention Center に行きます。
Dress Rehearsal とはいわゆるプラクティスなのだが、WF のプラクティスはオンラインで事前にあったのでこういう名前になっているらしい（自分の英語聞き取りが正しければ）？
APAC と比べると、ジャッジシステムが DomJudge から PC² になりました。まだ使い慣れないが、順位表を開いていてもジャッジの通知が見えるのとコマンドラインから提出できるのはいい感じ。

これまですべての食事がビュッフェ形式だったが、Day 3 から 5 までの昼食は事前の Lunch Survey で選ぶ形式です。ちゃんと回答した Ponjuice、なんでも食えるからサボった私、好き嫌いが激しいのに答えなかった愚かな simasima でお送りしていきます。

Dress Rehearsal の後は JetBrains 社の Tech Trek なるものがありました。2 人のつよつよ競プロ er が Kotlin で早解き対決をしていました。面白かった。

その後は夕食まで暇だったので、日本勢の一部で観光に行くことになり、バクーの旧市街を歩いたり高台からカスピ海を望んだりしました。帰りのタクシーが思ったより時間がかかり夕食を逃してしまったが、Chill Zone（人々やスポンサーが屯しているエリア）に食べ物があり助かりました。

Ponjuice がスーツケースの鍵を失くしたらしいです。超ウケる。

Day 4 - ICPC Challenge

この日は本当に ICPC Challenge しかありませんでした。ICPC Challenge とは、なんか WF についてるおまけのコンテストで、AHC 的な問題を 3 時間で解くらしいです（前情報）。

今年は写真をいろいろなサイズに拡大して幅 $K$ の長方形に敷き詰めましょうみたいな問題です。スマホや PC の写真アプリ的なのをイメージするといい。

テストケース生成コードが配布されるので読むと、制約では $2$ から $16$ となっているものが $13$ から $16$ になっています。なんで？？？

評価関数は、入力で与えられる「この画像をこのサイズで使うと $x$ 点だよ」と、各サイズの個数の標準偏差と、全体の長方形の高さと、画像のふちが T 字になっているところの個数で決まります。

いろんなサイズを採用しようとすると、最終的に長方形に収めるのが難しくなって困る。

Ponjuice 先生が、高さが等しいものを 1 行に並べる DP を書いて、20 位でした。
私と simasima は別の手法を考えたりしていたが、3 時間で 2 つの解法を詰めて実装するのは不可能なのでどちらかに集中するべきだった。

改善点としては、DP で形の並べ方を確定させた後に画像を swap する山登りが考えられます。どうせ山登りするなら、山登りで変化しない標準偏差と高さとT字の個数に重きを置いて初期解を作るべきな気もします。

東大が 1 位を取っていてすごかった。2 連覇？

そのあとはしばらく暇だったので、Huawei から数独をもらって解いたりホテルに戻って京大コーチのなにわづさんとチェスを指して負けたりしました。
チェスライクなゲームが超久々で、何回か意識外から相手の駒が飛んできて全然ダメでした。

夕食後にチームの 3 人で序盤 1 時間だけの練習をしました。ペナ は出なかったのでいい感じ？

Day 5 - ICPC World Finals

本質の日です。

順位表: https://worldfinals.icpc.global/scoreboard/2025/
問題文: https://worldfinals.icpc.global/problems/2025/

いつものように起きて会場に移動します。Regional などの運営をされている東大の山口先生や科学大の西崎先生と遭遇したのでちょっとだけ会話をしました。

競技は若干早く始まったような気がします。日本語の配信もあったので見ましょう。

我々のチームは、simasima が考察した問題をどちらか 2 人に伝えて実装することで、simasima が常に考察をしていることができるという戦略で、ハマったときはかなり上振れを狙えると思います。

初動では、私は前から読んでいくことになりました。

A: 変な手順で作られたヒープから、ヒープに入ってきた順番を復元する。見るからに難しいあるいは面倒そうだが、一応 simasima に伝える。
B: $1$ から $n$ の整数が書かれた黒板から数字を交互に消していくゲーム。直前に消されたやつの素数倍か素数分の 1 が選べる。simasima が好きそう。
C: なんか理由は忘れたが飛ばす。
D: 惑星探査機のプログラムが宇宙線でバグるので、最低何回バグったかを答える問題。制約も小さいし簡単そう

この間に Ponjuice が L を通している。

ここで simasima から F の解法を渡される。若干正当性に納得できなかったが、まあ反例もすぐに浮かばないので実装する。
F の解法: 植物 $i$ が置けるかを管理しながら前から見ていき、置けるものの中から適当に置く。置けなければ NG。

若干バグらせた記憶もあるが無事通る。D は全探索でいいらしいのでそのまま実装をする。
サンプルが合わず、誤読が発覚する。バグって探査機がランダムな方向に動くのかと思ったが、なんとバグるとプログラム全体がランダムに書き換わるらしい（宇宙線強すぎだろ）。
すぐに DP を思い付き、コードも誤読したやつを部分的に再利用したので割と速く直って通る。

この時点で順位表では BIJ が解かれており、IJ は既に考察済で Ponjuice に渡されている。
適当にまだ誰も読んでいない問題を読んで過ごすことにする。
H: ゲームの得点板を作る問題。$n$ 元集合が与えられるので、それらの和で表せて $m$ 以下の整数をすべて表現したい。0 から 8 の板がそれぞれいくつ必要か？（9 は 6 の板で代用できるので不要）

K が通されたらしいので読む。
K: 2 次元格子の格子点対してに深さ $d\ge 0$ が定義されている。各単位正方形は平面になっている（つまり、対角線の深さの和が等しい）。いくつかの格子点の深さが与えられるので、$(t_x,t_y)$ の深さとしてあり得る最小値を求める。
simasima に伝えると、「全て $0$ の状態から各列/行を任意に増やしたものになっている」とだけ言われる（B に集中したいらしい）。これを軸にちょっと考えるとすぐに解法が生える。

Ponjuice は I を通し、J で沼っていた。パソコンを代わってもらって実装する。最後のパートの考察が少し不足していたが、すぐに解決して通る。J もほどなくして通っていた。

H の解法が飛んでくる。ある程度大きい数は gcd の倍数ならすべて作れるので、小さい部分は愚直にやって大きい部分は 「1 を $k$ 個使う得点」みたいなものを全探索するらしい。
計算量が不安だったので実装しながら考えていたら、大きい部分は桁 DP で行けそうな感じなので、その方針に切り替えて実装する。leading zero の扱いが面倒。桁を回すループが 0 から 8 になっているカスのバグを埋めたが、気合で気付いて 1 発で通る。

A も解かれて、順位表凍結時点で 8 完。順位表を見ると、遅めの 9 完ではメダルが取れなさそうなので BE で 10 完を目指すことになる。
2 人は B に集中しているので 1 人で E を考える。解けた気になって提出するが WA が帰ってきて、Ponjuice に解法を説明して反例ケースをもらう。修正を考えていたらコンテストが終わってしまった。

Yes/No は事実が開示されるだけなので割愛するが、1 位が単独 11 完ですごい。東大が 2 位なのもすごい。
Ponjuice だか徳山高専の sounansya さんだかが「これ見れただけで満足」と言っていたが、さすがにそんなわけないだろ。

我々のチームは 27 位でした。

コンテストの感想

チームとしては、大失敗でも大成功でもない平凡な結果に終わってしまい、ネタとして弱い。
個人的には、多少のバグは埋め込んだものの実装マシーンとして求められた仕事はこなせたし、HK の考察も進めたので貢献できたと思う。

E の方針は割と合っていそうなのでワンチャン解けたな～と思いつつ、序盤が遅いので 9 完でもメダルに届かず、完全敗北という結論に。

ところで、だいたい 8 完がメダルの目安と聞いていたのですが？？？

Day 6 - 帰る

Day 5 の夜に Hollow Knight: Silksong が各種プラットフォームで発売されました。開発元の出すよ出すよ詐欺で数年待ち続けたゲームなので、当然 ICPC よりもワクワクしています。早く帰って遊びたい。

朝食を食べ、ホテルの周りをちょっとだけ散歩します。カスピ海、見渡す限りの水なのに波が全然無く面白い。湖だから潮汐とかの概念が無いのだろうか？地学はよくわかりません。

帰りもドーハで乗り継ぎですが、着くのが成田です。どうやら東大チームも同じ飛行機のよう。別に行きと変わらないのであとは特に書くことがないです。
というのも、この部分はドーハで書いています。日本に帰る前に参加記を完成させて、何も考えずにゲームできる環境を用意！

感想

コンテスト自体は微妙な結果だったが、普通に面白かった。また参加したい。
今回は Bill とのツーショットを撮るのを忘れたので、次は撮ります。たぶん必ず。

あと、スマホもスーツケースの鍵も失くさずに済んでよかったです。