ICPC 2025 国内予選 参加記（チーム Magical Fish / miscalc 視点）

はじめに

2025/7/4(金) に行われた ICPC 2025 国内予選で 7 位となり、アジア地区に進出することができました！ ずっと念願だったのでめちゃくちゃ嬉しい。

チームメンバー

全員が 計数 → 情報理工の数理情報学専攻 M1（ラストイヤー！）。ちなみに confeito と私は研究室まで同じ。

• confeito：AtCoder のレートが 2300 くらい（昨年比 +200）とチームの中で最も高い。ARC が得意。幾何ができる貴重な人材。提出前の確認がかなり慎重で助かっている。とても頼りになる。

• serendipity_：AtCoder のレートが 2100 くらい（昨年比 +200）。CF にも熱心に出ていて 1 回薄赤タッチしていた。構築が非常に得意。謎の実装問をいつの間にか通していることも多々ある。とても頼りになる。

• miscalculation53：筆者。AtCoder のレートが 2000 くらい（昨年とほぼ変わっていない←え？）。他の 2 人に比べると ABC が得意で知識ドリブンのアプローチをすることが多い。

他 2 人が真っ当に ad-hoc が得意なのに対して私は機械的な解き方のほうが好きだったりといい感じに特性が分かれていたり、競プロへのモチベが大体同じくらいだったりして（所属が同じだから忙しい時期なども被りがちだし）、相性は結構いいチームだと思っている。

1 年間の取り組み

昨年も同じチームで参加したが国内予選で敗退し、とても悔しかった。そこから 8 月までは 3 人とも院試の勉強で忙しかったが、院試の終わり際に SSRS さんからこんな誘いがきた。

というわけでいつもチーム練をしていた工学部 6 号館で、都合がつく人で集まって CF Div.1 ばちゃをやっていた。レッドコーダーの頭脳をめちゃくちゃ贅沢に使わせてもらってかなり最高の時間だった。強い人が何考えてるか聞くと 1 人で upsolve するだけでは気づけなかった視点が得られて非常に素晴らしい。私以外の 2 人はおそらくこれのおかげもあってレートが上がっていて、私はレートこそ上がっていないもののできることは増えているはず（だと信じたい）。SSRS さん本当にありがとうございます。

あとは同時期に UC にも出始めた。UC は難しすぎるという噂を聞いていたがこれはかなり回によっていて、難しいときは手も足も出ないこともあるものの、黄 * 3 くらいでも十分楽しめるくらいの難易度であることのほうが体感多い気がする。これでチーム練をたくさん積んだことによってお互いの特性や得意不得意、チーム戦での立ち回りなどについてかなり理解が深まったと思う。

国内予選が近づいてからは、CF Gym で見つけた 3h セットをよく走っていた（過去の国内・模擬国内は昨年の練習でほぼ消費していたため……）。我々 3 人チーム vs SSRS さんソロ で 3h セットを並走したりも数回した。ただ、そもそも 3h セットが少ない上に、難易度順でなかったり国内と傾向がだいぶ違ったりといった点でも困っていて、国内の対策になっているかは少し不安でもあった。

CF ばちゃ・チーム練のどちらも、暇なときはだいたい週 1 くらいだったが、卒論等で忙しかったりして自然消滅する時期もあったので、平均すると 1.5 〜 2 週に 1 回くらいのペースだったかな？

戦略

ICPC 攻略法：国内予選編 - クマーの競プロ精進日記 を読んで、ほとんどの場合 2 人以上でやる、という部分に非常に共感したので、その戦略をとることにした。これでいくつか 3h を走ったところ割と手応えがよかったので本番もこれでやることにした。結果的に本番でもこれが守られていて、実際にうまくいったのでよかったと思う。

本番直前

模擬国内

模擬国内ではかなりうまくいって全体 7 位、現役内 4 位だった。しかし序盤のペナが多い、構文解析が苦手、などの課題も見つかった。

ペナについては、序盤でも慎重に行き、一瞬だけでも誰かの目は必ず通すことにしようと決めた。

構文解析については直前のチーム練でも出てきていて、うちのチームは confeito に丸投げすることにしていたのだが、彼が時間がかかっている間他 2 人が完全に蚊帳の外なのは割と問題があると感じた。そこで私が個人的に構文解析を練習した。（ICPC に出題されてみんな解くような範疇の）構文解析なら 1-2 時間で余裕で習得可能であることが判明して、これなら全然今までやっておけばよかったと思った。出題されなくても不安要素の払拭になったのでこれはやってよかったと思う。

東大内の枠争いについて

東大チームがなぜか誰もメンバー情報を書き込まないが、実は東大内では誰がどこにいるかはお互い完全に把握していた*1。チームメンバーのレート的に完全に格上なのは 217 と SSQS の 2 チームで（この 2 チーム間の比較もよくわからないが私は勝手に同じくらいかなと思っている）、あとはレート的に同格くらいのチームもいくつか、といった情勢で、217 と SSQS 以外に勝てば学内 3 位で通過できるかな〜とか言っていた。一方で、東大内で最もチーム練を（今回のメンバーで）してきたのは自分たちだろうとも思っていたので、単なるチームレートにとどまらないチーム戦の練度といった点でアドをとっていきたい、あわよくば 217 や SSQS にも勝ちたいとも考えていた。

環境構築

東大の ICPC 国内予選では基本的に学内にある ECCS 端末を使うことになる。これが結構曲者で、競プロ目的だと実質的に macOS しか使えないのと（これだけならまだよいが）、何かをインストールしようとするたびに管理者権限を要求されるのであらゆるものが入れられない。特に clang しか使えないのと VSCode の C/C++ 拡張がまともに動かず補完がきかないのがかなり困る。

clang については #include <bits/stdc++.h> がそのままでは使えないという問題がある。これは bits/stdc++.h のファイルをそのまま持ってきて -I オプションでインクルードすることで解決した（これは昨年からだが）。また、oj-bundle がそのままでは動かないようだ（よくわからなかった）。いろいろ試行錯誤したが、結果的に tatyam さんのツイートにある -E オプションで展開する方法を使うことで解決した。

( echo -n "#include <bits/stdc++.h>"; clang++ -nostdinc -fdirectives-only -E -P a.cpp ) > expand.cpp
で展開ができる！ https://t.co/fVLLMndyNo

— tatyam (@tatyam_prime) 2025年6月30日

補完については妥協して、"editor.wordBasedSuggestions" だけ動くようにした。後で聞いた話によると C/C++ 拡張をアンインストールして clangd をインストールするとうまくいったらしい。

このように環境が特殊なので、環境構築をした後は環境に慣れるために ECCS 端末で簡単めの 3h セットを走った。これはかなりやってよかったと思う。

またこのような状況なので、自前の端末を使用することにしたチームもあったようだ。これだと印刷機が（問題文の印刷以外で）使えなくなるという問題があったり、また単純に画面が小さいなどの不利益もあるので、総合的に判断した結果我々は ECCS 端末を使用することにした。

本番

始まる直前、私は緊張で心臓バクバクだった。他 2 人もそれなりに緊張していそうだった。でも緊張するということはそれだけ今まで練習を頑張ってきたということでもある。練習をまともにせず出た 2 年前とか一切緊張しなかったし。終わってからだから言えるのかもしれないが、このヒリヒリ感は案外悪くないと思う。

問題 PDF を開く。A を斜め読みし、B にスクロールさせて A を書き始める。テストケースの形式が今までの国内予選形式だったのは個人的に少し意外だった。ここでペナを出してもいけないので（bundle 後のコードが正しく動作するかも含めて）慎重に確認し、提出。AC (A 0:02)。

B を seren が書き、C を confeito が考える。私があまり概要を知らないのに変な口出しをしてしまってちょっとロスをしてしまったが通る (B 0:06)。

C を confeito が書き、D を seren が考える。私は C の見守りと D の考察の間くらいのことをする。ほどなく C も通る (C 0:12)。

D の考察を seren から聞き、それなら私が用意していたランレングス圧縮ライブラリを使うと実装が短縮できそうということで私が実装することに。テンプレに入れておいたグリッドの転置も役に立っていい感じだった。ただ正当性が怪しそうと感じたため「本当に大丈夫？」と 2-3 回くらい確認した気がする。不安だけど大丈夫な気がするなあなどと言いながら提出したが、WA が返ってきてしまう。

この間に E を考えていた confeito が解けたというので概要を聞き、その間に D を直す方法を考えてもらうことに。E は雰囲気正しそうと伝える。

D の反例と直す方法がわかったというので実装する。これで網羅できているかはそこまで自信がなさそうだったが、他に特に思いつかないので信用することにして提出する。これで WA だったら沼で嫌だな〜と思いながら提出すると通って安心した (D 0:29)。たしかこのあたりのどこかで印刷問題文がきたような気がする。

E を confeito が書き、F を seren が読む。私は E の見守りをしながら F を読んだりした。入力形式を間違えていることに提出直前に気づいたりしてかなりひやっとしたが、結果的に問題なく通って 3 位に浮上 (E 0:41)！ このあたりでは順調だと感じていた。

このあたりではあんな難易度のセットだとは思いもしなかったので F に 3 人を割いていた。私も話を聞いていたが途中でよくわからなくなったので離脱して雛形を書くことにした。実際に操作をすると同時に出力すべき操作列を更新する関数を書いた。こういう構築はこれをやるとデバッグやランダムテストがしやすくなってかなりいいと思う。その間に解けたというので seren に実装を渡して、実装を見たりランレングス圧縮ライブラリの使い方を教えたりしていた。書けたようだが、怖いのでランダムテストを私が書いてから提出する。通る (F 1:05)。例年通りならもう通過できるだろう、早くコンテスト終わってくれ〜などと思っていた。

G は confeito が解けそうと言っていた。一瞬 3 人で見ていたが私は幾何の図が見たくなさすぎて逃亡して H を読んで考えていた。その間も G の実装をチラ見して気になったことを伝えたりした。たとえば 10'000'000'000 と書いていたが LL つけなくて大丈夫？ とか、あまりをとっているところ負になる可能性はない？ とか。これらはもしかしたら結果的に何も変わらないのかもしれない（変わるのかもしれない）が、こういう場面（書き方 1 と 2 があって、私は普段 1 を使っているが 2 でも大丈夫そうな気はしていて、今 2 で書かれている）はすべて口を出して、すべて安全側の 1 に倒すという方針にすることにしていた。実際今までこれを言い渋ってペナったことはたくさんある（前日の練習でも踏んだし、負の除算は昨年の G で実際に踏んだ苦い経験がある）。これが効いたのかどうかはわからないが、G が無事通る (G 1:30)。

このときも早くコンテスト終わってくれ〜と思っていたが、H は簡単そうと感じていて、I も読んだ感じ実は簡単がありえそうな上に The Revenge of Shinchan が通していたため、まだ頑張らないといけないのか……と思って軽く萎えた記憶がある。そんなことを言っても仕方がないので H の考察の初手（偶奇と、連続しているところに行けたらだいたい OK）を 3 人で共有する。大枠はわかるけど細かい部分がなかなか詰められず、焦る。

途中順位表で追い抜かれまくっていてかなり焦った。でも順位表を見ていてもどうせ全員で H を見るという戦略は変わらないだろうということで、confeito の提案で順位表を見ないようにした。これをやったおかげで H の考察に集中できた面はあり、やってよかったと思う。

H は結局「2 連続以上に到達できるかどうか」みたいな bool 配列を作っておくとよさそうという話になった。配列の作り方を 2 人が議論していたがよくわからなくなったので、自分はサンプルを眺めてその配列や答えを手計算して、その方法で本当に正しいかを確かめることにした。これのおかげでこの配列を作るパートのデバッグがかなりスムーズにできた上に、答えを求めるパートの実装（私がやった）も比較的スムーズにできた。というか D, F に続いて H でもランレングス圧縮ライブラリが大活躍で、ランレングス圧縮多すぎない？ 結果的に少し時間がかかってしまったが、無事ノーペナで AC (H 2:15)。

これで通過が確定してほしいところだったが、順位表を見ると I も結構通っていて、もし RecEight あたりが全完した場合落ちてしまう状況だった。こんなふうにこのコンテスト、AC して「これは通過だろ」→「えーまだ考えないといけないのか……」がずっと続いていて本当に苦しかった。I を考えるけど手がかりがあまりつかめない、そもそも permutation じゃない場合があるのやばくない？ となる。実はコストがペアの距離の和とかだったりしない？ と適当を言ったところで、これってあの 321 の嘘転倒数のやつに似てるよねという気持ちになって、問題そのものがなんか転倒数風味がするみたいなことを言う。このあたりのどこかで seren が、同種を swap しないからマッチするペアが簡単にわかって permutation の場合に帰着できる、ということに気づいて、そうじゃん賢すぎ、となる。その後しばらく考えていると confeito が「これって線分の交差数じゃない？」と言い出した。え、めちゃくちゃそれっぽい……！ いくつか例を見てみても正しそう。これで正しかったら Rectangle Sum で解けますねと私が指摘して、残り時間も少ないし正しそうな気がしていたので、実装することにした。弦の交差の条件覚えてないな……と思って 2 人に投げてその間にペアを決めるパートの実装をしていたけど、結果的にこれは担当逆のほうがよかったかもしれない。交差の条件を Rectangle Sum に落とすパートで少しぐだった上に、Rectangle Sum ライブラリの使い方も間違えていて*2ぐだってしまった。これがすぐ書けないのは反省だな……。それでも間に合わないほどは遅くはならなくて、終了 5 分前に投げる。AC して通過が確定 (I 2:55)！ めちゃくちゃ嬉しかったと同時に開放感がすごかった。

結果的には I が通っていなくても通過してはいたのだが、全完できない上に 10 位以内に入れないが学内 3 位なのでセーフ、だとしたらかなり後味が悪かっただろうから、I を通せて本当によかった。I は特に 3 人の考察が全部効いてきていてこれぞチーム戦、という感じだったのもとてもよかった。

おわりに

ついに念願の国内予選通過を果たすことができた。コンテストとしては、チーム戦らしい完璧に近い立ち回りができて、実力が発揮できて本当によかったとともに、チーム戦の面白さを実感した。B2 くらいの暇だった頃に比べると忙しくなってはいるのだが、その合間を縫ってこの 1 年間 ICPC のために 3 人 + SSRS さんの協力で頑張ってきた甲斐があったなと思う。とはいっても、まだまだ ICPC はこれからなので、さらに精進して、赤がいるようなチームとも渡り合えるような力をつけていきたい。横浜で会う皆さんよろしくお願いします。