ICPC 2026 国内予選参加記 (Chronus:caz37OwO視点)

概要

ICPC2026国内予選の、caz37OwO視点の参加記です

ICPC2026国内予選にチーム Chronus で参加し、全体9位/学内2位で無事予選突破することができました！

チームとしては A~H の8完でした。

やった～

チームメンバー

rice_tawara459 （こめだわら）さん

他二人より年上でAtCoderのレートも一番高く、自然とチームのリーダー枠な存在です。本番では考察+一部の実装を担当してくれました。とっても頭の回転が速いくて、すごい（小並感）。

rhoo （jibjib）さん

ヒューリスティック最強です。それに伴ってタイピング速度がめっちゃ早く、一定の重実装耐性もあるらしいため、本番では実装担当をしてくれました。多分Rust使いだったのにチームに合わせてC++で実装をしてくれました。感謝。

caz37OwO

筆者です。B2ですがICPCとしてはファーストイヤーなので分からないことだらけで、チームメイトに色々教えてもらいました。よく実装を爆発させがちなので、考察+一部軽実装を担当しました。

背景

なぜか今年は暖色を含むチームが科学大に8チームもいたため、同校制限の4枠がかなり熾烈な争いとなっていました。全員黄以上のチームに絞っても5チームあり、どのチームが落ちてもおかしくないような状況でした。

~~あとなんでこの大学は38チームも出場しているんですか~~

模擬国内予選

実際に予選本番を行う演習室の鍵がないというハプニングのため、急遽別の場所で実施されました。

ICPC2026模擬国内予選ではA~Gの7完で全体11位（有参加資格者中9位）/学内3位で、突破ボーダーは踏めているような結果でした。

こめだわらさんがC,E,G(考察),H(考察)、jibjibさんがA,D,G(実装)、自分がB,Fを担当しました。こめだわらさんありがとう。jibjibさんありがとう。caz37OwOさん仕事しろ。

本番！

本番前

授業と予選がモロ被っていたため、 ~~授業ブッチ~~致し方なく予選を優先することにしました。

PCについては疎すぎるので、セットアップ諸々は完全に二人に投げて後ろでくねくねしていました。予選が始まる前はリハーサルが行われるので、そこでTLE,MLE,REやCEなどの仕様、出力時の余計な空白や改行はどう挙動するのか、など細かいところを確認しました。

確認が終わったあとこめだわらさんと大学近くのお店に昼食に行きました。初めて行った油そばのお店で、辛かったけどおいしかったです（が、本番中水分補給の回数が明らかに増えました、なんでですか）。

開始15分前くらいになぜかチーム zer0shiki が廊下でラジオ体操を始めて、軽く便乗していました。（これで気持ちリフレッシュできてしまった気がしてなんか悔しい）

コンテスト本番

当初の予定としては A:jibjibさん,B:自分,C:こめだわらさんと担当し、D以降は問題の傾向や進捗によって都度調整、みたいな感じでした。

A

jibjibさんが担当しました。A問題にしては場合分けが多く少し面倒そうにしていましたが、難なくCorrect(0:03)。

B

自分が担当しました。自販機をなるべく右に置く貪欲が正当です。無事Correct(0:04)。

C

こめだわらさんが担当しました。問題は見てないものの、チラッと図があるのが見えて実装が大変なタイプのCかなぁーと思っていたら、たった5分で実装を終わらせて一発Correct(0:09)していました。

D(1)

初めはjibjibさんが担当していましたが、うまい方針が立たなかったのか、こめだわらさんにバトンタッチしていました。実際Fが実装問題だったので、ここでDを渡す戦略は悪くなかったかもしれないです。

このタイミングでEが多分解けたので、PCを奪います。

E

自分が担当しました。サンプルケースで分かるようにジェム付きを連鎖的に購入することができるので、その方針で考えます。するとジェム付きを何個買ったかによってジェムの付いていない酒に何個ジェムを残せるかが決まり、それぞれ買うものは安い方から貪欲で良いと分かったため、ジェム付きを何個買うかを累積和を用いて全探索。途中で配列を取り違えていた（のにサンプルは合っている）というヒヤリハットはありましたが、提出前に気付けて一発Correct(0:26)。

終わってから改めて考えると、想定解では全探索すら必要なく、実装に無駄があったようで少し残念。

D(2)

Eの実装の間にこめだわらさんが紙に色々丁寧に場合分けをしていたようで、解く順番は前後したものの無事一発Correct(1:04)。なぜかこめだわらさんがコード書く前からランテスとか言っていて、何事！？と思っていました。

F(1)

Dをこめだわらさんに渡して、Eは自分がやっていたためjibjibさんは次のFを担当しました。ちょうど重実装だったのでなんか都合がいい。

建物の四隅から1マスずつ動いたグリッドを頂点にしたグラフを作ればいいという方針にすぐに気付いたっぽいものの、実装がかなり難しいらしく苦戦していました。そしてようやくサンプルが合ったので提出するもまさかのTLE。改めて計算量を考えると普通にダメだったらしかったです。ここでGの実装が軽そうだと分かったのでPCを奪いました。

G

こめだわらさんがDを実装している間くらいから考察を進めていました。

眺めていると、駒同士がぶつかり得るのは中心辺りのある 1列に限られると分かったため、うまいこと包除原理をコネコネすれば解けるだろうと考えます。ここでDを通したこめだわらさんから「初めてぶつかる地点を考えればいい」と助言をもらって、それを基に考察すると、実装量の少なそうな簡単な計算でいけそうだと分かりました。

手元で小さなケースでdpを回して細かいところ計算式を詰めつつ、Fの実装の隙を見てjibjibさんからPCを奪い無事Correct(1:18)。

H

F(1)の実装中に、H問題の考察も進めました。最初は確かこめだわらさんが考察していた気がするものの、bitDPが回りそうな制約とだけ聞いて自分が引継ぎました。

考えると、各棒の挙動としてあり得るのは「最後の同色の塊を残す」か「全ての浮き輪を外す」であり、どの順で棒が消費されるのかの順列全探索+bitDPで $O (N! \cdot 2^{N})$ で動きそう（計算量的にはOUTだが…）だとなんとな～く思います。逆にどの順で色を消費するのかの順列全探索+bitDPも回りそうで、ここで棒・色どちらも同時にbitDPを行えば $O (2^{N} \cdot 2^{N}) = O (4^{N})$ でちょうどそれっぽいと気付きます。

遷移もそこまで複雑ではなく、実装自体は落ち着いてやればそこまで重くなさそうだったので、Fのキリが良くなったタイミングでjibjibさんからPCを奪います。5重ネストくらいしたものの、ほぼ一発でサンプルが合ったため、お祈りしながら提出するとまさかの一発Correct(1:35)。

$O (4^{N})$ （正確にはちょっと違うけど）のbitDPとか初めて見て、問題としておもしろ～いって思いました。

F(2)

四苦八苦しながらオーダーを $O (m^{2} q)$ から $O (m q)$ に頑張って落として、ようやくCorrect(2:18)。コードは見た感じ200行くらいはありました、jibjibさんありがとう。

I

こめだわらさんが担当しました。議論のサンドバッグになるつもりが、全然追い付けなく申し訳ない…。方針としては解けていそうでしたが、だいぶ重実装でバグを生みやすく、サンプルがなかなか合わない。そしてなんとかバグを見つけてサンプルが合ったため、提出したものの残念ながらWA。その後もクリティカルなバグが見つからず、間に合いませんでした。

後で解説をみたらやはり方向性としては正しかったらしく、惜しかったです。

結果

A~Hまでの8完で、全体では9位/335チーム、校内では2位/38チームと、無事予選通過することができました！

全体として解くべき問題をちゃんと通し切ることができ、予選通過ボーダーとも完数差を付けることができました。ペナも一つだけで、丁寧に実装できて偉いです。重実装をチームメイトに丸投げしてしまったのは申し訳なかったですが、それらをちゃんと通してくれたチームメイト二人には感謝しかないです。

科学大全体としては、寒色チームが逆転することはなく、順当にAtCoderの平均レートが高い順に通ったという感じがします。が、zer0shikiとsshがボーダーを1位差で争う重い勝負があったようで、だいぶ苦しい。他には26Bのみで構成されているRGBが学内6位で、強いなぁーと思いました（小並）。打倒Phantasmには失敗。

最後に

チームメイトのこめだわらさん・jibjibさん、コーチをしてくださったshobonさん、国内予選のスタッフの方々などにはとても感謝です。横浜でも頑張ります！！！