はじめに

ICPC 2024 Asia Yokohama Regional に AMATSUKAZE というチームで参加して 4 位でした。

チームメンバーは以下の通りです。

• noya2 (B3) 筆者
• shobonvip (B4) 昨年のチームメンバー
• Hemimor (M2) 昨年の tonosama のメンバー

ICPC の簡単なルール説明

よくある流れ： 国内予選 -> 地区大会 -> プレーオフ -> 世界大会

すべてのチームが世界大会 World Finals (WF) に向けて頑張ります。

同じ大学から WF への出場権を得ることができるのは 1 チームのみです。

地区大会 Regional での優勝チームは WF に出場できます。（ほんとうは少し複雑、詳細は省略）

Regional で優勝できなかった上位チームは playoff に出場して、追加の WF 出場権を争います。

国内予選から本番まで

国内予選は 1 位でした。

11 月に開催された韓国の Regional に参加して 5 位でした。 WF への切符を得るための遠征だったので優勝しか狙うものがなかったのですが、優勝は叶わずでした。ただ、この時点でプレーオフに出場する権利をほぼ獲得します。

ほぼ、というのは、同校制限があるので、他の同大学チームに地区大会で優勝されると困ってしまいます。つまり、Yokohama で目指すべきは、まず 同大学チームの優勝阻止 です。とはいえ、優勝を目指しておけばOKです（十分条件なので）。

day1

Regi & リハーサルです。CLion の使い方を復習します。東京大学の強豪 Screenwalkers が隣の席にいるのを見て天を仰ぐなどします。

day2

本番です。すべてのチームが Check In を済ませたところでほぼすぐにコンテストが始まりました。

本番 (5h)

自分は環境構築をします。

• PCにログイン
• Clion のセットアップ
• テンプレートを書く
• エイリアスを貼る alias icpc='g++ -std=c++20 -O2 -Wall'

A を shobon さんが解いていたのですぐに実装してもらいます、通ります。

B を Hemimor さんが解いてくれていたのですぐに実装してもらいます、通ります。

どちらもそこまで時間をかけずに通してくれました。

K を Hemimor さんが解けたらしいので、その時点では FA がまだ出ていませんでしたが、実装してもらいます。WAが出ます、困りました。いったん離れてもらい、 shobon さんが E を書きます。面倒らしいですが通ります。

すいません、まだ何もしておりません。とりあえず Hemimor さんから I をもらって考えます。オフラインクエリなのでとりあえず $r$ でソートしてしまいましょう。約数 $d$ について直近の $2$ つ目の位置を持っておけば良いです。約数列挙は $\le 10^5$ の制約から $O(\sqrt{a})$ を実装することします。shobon さんに segtree を写経してもらいます、爆速で終わりました。 d * d == a のときの更新処理をバグらせており 1 ペナをつけますが、通りました。

ほぼ同じタイミングで K のコーナーケースがわかったらしく、修正して通っていました。

隣で C の議論が行われています。大胆予想があり、正しそうであり、実装に移るか悩んでいるところでしょうか。

自分は問題文の 2 ページ目に 998 の文字が見えたので迷わず D に挑みます。 1 ページ目を見て、構文解析かーい、と掌を返したくなる気持ちを抑えて問題文をよく見ると構文解析は無であることがわかります。操作はマージ過程を表す木ですが、区間のマージに置き換えて良いです。任意の $i|i+1$ の仕切りがちょうど一度マージに寄与することを考えると、簡単な総積の式で答えが書けることがわかります。

C が通りました。自分は D の実装に取り掛かります。構文解析パートは無ではあるものの、あまり書いたことがないので少し時間使って丁寧に書きます。バグらなかったのは良かったですが、WAが出ます。頭が壊れていましたが、サンプルが奇跡的に壊れた頭を hack しており、サンプルを全部通過してしまっていました。ごく普通の修正をして AC します。FA (First Acceptance) でした。これ以降、何もしていません。

G が可能そうなので見ます。水流のように考えて、ある領域の収支を考えると、縦に区切って二分探索する方針を思い浮かびます。クエリ回数がやばいので改善する必要がありそうです。縦横に区切ればクエリ回数が線形になりそうですが、よくわからなかったので（え？）Hemimor さんに投げます。

L を shobon さんから聞きます。意味不明ですが、いろいろあって、区間内の操作回数の最大値に注目するのが良さそうということがわかったので、それを伝えます。ほぼ同じ結論に辿り着いていたようです。自分はその後 J も聞き、 L は　shobon さんにお任せします。

J を考えます。LP です。双対をとっても良さそうですが、次元が減りません、困りました。捨てるまでにかなりの時間を使いました。

Hemimor さんが G を解けたらしいです。実装がやばそうですが、書き始めてもらいます。

L で shobon さんと壁打ち（自分が壁）をしながら、実装できそうなところまで詰めてもらいます。

かなりかなり大変そうですが、G の実装が終わったらしく、いくらかデバッグをし、投げて、 WA が返ってきます。困りましたが、すぐに撃墜ケースを見つけたようです。印刷してコードと睨めっこしてもらいます。

L の実装をしてもらいます。いろいろ実装して、デバッグをして、投げて、WA が返ってきます。困りました。撃墜ケースをすぐに作ることができず、よくわかりません。自分は実装を完全にお任せしているので、考察ミスしか疑うものはありませんでしたが、多分大丈夫だろうという結論に至りました。

G の大変なデバッグ作業が終わり、ようやく撃墜ケースも通るようになりました。Hemimor さんは自信がありそうだったので、提出してもらいます、AC です。すごい！これは本当にすごいです。

実はこの時点で Screenwalkers が強すぎて優勝はかなり絶望的でしたが、同大学内の 1 位は現実的になってきました。

F は初手で見てやばい数学だと思ったので飛ばしたのですが、徐々に AC が出始めたので取り組むことにします。結局のところ、直方体の表面上の任意の点についての距離を求める関数を用意すれば良さそうです。各面については距離は山形になっていると予想したので、これが正しければ三分探索を入れ子にすれば良いです。任意の経路を取ることを考えますが、11 通りの展開図をすべて書く方法を思いつきます。やりたくないので別の方針を考えていると、 Hemimor さんに考える点を 90 度回転していってすべて試すような方針を教えてもらいます。これならすぐ実装できそうなので、L に変わって実装を始めます。

書けました。全然サンプルが合いません。致命的に合っていません。すべて合っているコードを書いたつもりなのですが。考察ミスを疑います。空間把握能力が足りていないのか、どういうミスなのかの見当が全くつきません。

困った〜

L と交代でデバッグをしていきます。正直なところ、自分はデバッグの段階ではなくて、考察ミス 8割 実装ミス 1割 頭破壊 1割を想定していてどれが原因かを探っている状況でした。結果的には頭破壊で、必要な経路を十分に列挙できていませんでした。

L の撃墜ケースが作れません。ランダムチェッカーを書きますが、全く落ちないらしいです。本当に困りました。自明なミスを直したので差分が出るはずだったのですが、全く出ずに困ります。

時間がなくなってきて、 F も L も焦っていたのですが、ここで諦めてコード自体の差分はあるので L を出すと、なんと通りました。そんな〜。落ちないよ〜と言っていた時間が無駄だったということになり、ちょっぴり悲しいです。いずれにしても通ったのはすごいです。凍結後の AC を出すことができて、これもまたワクワク要素に寄与できて嬉しいです。

順位発表

凍結後に L を AC して 9 完 4 位でした。優勝はできませんでしたが、同大学内の 1 位を取ることができました。

懇親会

色々な人と交流しました。東京大学のチーム SPJ に勝てて嬉しかったので、そのことを伝えに行きました。それから、筑波大学のチームや京都大学のチーム。慶應大学のチームなどと交流をしました。問題の解法について話し合ったり、TTPC2024の宣伝をしに行ったりしました。JAG のスタッフの人や ICPC ジャッジの人ともいくらかお話をさせていただきました。ありがとうございました！

おわりに

来年の 2 月末 ~ 3 月上旬に シンガポール で行われる playoff に出場します。よろしくお願いします。