ICPC2025 Prelim 参加記
Updated: 2025-07-13
はじめに
ICPC2025 国内予選にチーム Maximum Masters で参加し、全体40位で予選通過となりました！
チーム名はメンバー全員が埼玉大学プログラミングサークル Maximum に所属している M1 であることからこの名前になりました。
みんなラストイヤーでしたが、今年もこのチームメンバーで予選通過できて嬉しいです！
チームメンバー
- a01sa01to :AtCoder 青
- through : AtCoder 青
- kAsA02 : AtCoder 緑
a01sa01to の読解速度と実装速度が非常に速いので、我がチームの戦略は、初動の読解と実装全般を彼に任せ、他の二人は C、D 問題を先読みします。そして、A、B 問題を爆速で解き終えた a01sa01to にスムーズに内容と考察を伝え、E 問題以降は全員で考察を進めるというスタイルです。
前日まで
ICPC に向けて何かやったか、と言われるとあまりやらずに、気付いたら ICPC の日がすぐそこに来ていました。チームでの練習は模擬国内予選に参加した程度で、個人としては典型90問の★6を埋めたり、サークルで開催されるICPC形式のバーチャルコンテストに参加したりして、個としての実力を鍛えていました。
模擬国内の結果は全体 32 位・現役内 20 位でした。 結果はそこそこ良かったものの、本番より好条件なオンライン参加だったことを考えると、まずまずといったところでした。
E で構文解析が出て、a01sa01to に構文解析部分を書いてもらい、それ以降は自分が解くというムーブが出来たのは協力プレイっぽくて良かったです。 F は DP は直ぐ思いつき、次元数を削減すれば間に合うというのも分かったが、A から決めていく DP を考えて実装し、サンプルは通ったが嘘解法で破滅。解説を見て後ろから DP するというのを見て確かに…となりました。嘘解法の危険性を本番前に体感できて良い機会になりました。
国内予選
当日は 13:00 に会場集合とのことで、私は 13:30 頃に到着しました (?)
とりあえず集合後にリハーサルの問題を解きます。 a01sa01to が実装をするので、彼の PC で参加していますが、彼の PC が US 配列で私は US 配列の記号の位置が一切分からないので、毎回 "=" や "+" はどこを押したら入力されるのかを全探索していると、それを見て笑われていました。
リハーサルをやり終えた時点でまだ 2 時間以上も時間が余っていたので、マリオカートや寿司打をして遊んだり、今年は私たちのチームが問題印刷係だったため、初動の動きについて話し合っていました。結局 kAsA02 が印刷された問題を他のチームに配ってくれることになり、私は先の問題を解くことに専念しました。感謝。
時間が迫ってきたので暇潰しを辞めて、開始の合図を待ちます。 いざ尋常に勝負！
A
開始後問題を見始めて 10 秒ほどで私が A の初め数行を見てると、既に a01sa01to が実装を始めていた (早すぎ) 最初の 2, 3 問は彼の独壇場なので、見るのを辞めて C, D を見ることにした。 いつも通り 1 問目は一瞬で AC (0:01)
B
a01sa01to にほぼ丸投げ。少しバグっていそうでしたが無事 AC (0:07) ここらへんで kAsA02 が印刷周りを終えたくらいで、C はすぐに分かったので D を見てもらう。
C
先に読んで「やるだけ」だと判断し、問題の概要と「単純な算数で解ける」という方針を a01sa01to に伝えた。 最初はサンプルが通らなかったが、少し誤読をしていたことに気づき修正して AC (0:13)
D1
先に読んで考えていたが、とても面倒くさい…。 初めは正方形の一辺の長さ、一番左上にある正方形の角が集まる場所を全探索して判定とかを考えていたが、矛盾は判定できるものの一意に特定可能か否かの判断ができないな…となっていた。 結構時間が過ぎてしまい、このまま D に固執すると不穏な香りがしたので、kAsA02 に D の考察を任せて、自分と a01sa01to は一旦 E を見に行くことに。
E
グラフということで、比較的グラフは好きな分野なのでこれは解きたいなーと思っていた。 少しして、各時点で最も条件がタイトな航路を渡りに行くのが最適そうなことに気づく。 条件として到達済みマスからの最短距離と航路の最終搭乗期限の二つが大事になるが、最短距離が 1 遠いのと搭乗期限が 1 早いのは厳しさ的に等価なので、各時点で '最終搭乗期限 - 最短距離' が最小の航路を通るようにするのを、通ったことが無い航路が無くなるまで BFS をすれば良さそう。 この方針を a01sa01to に伝えると合っていそうとのことで実装をしてもらう。 少し実装とバグ取りに手間取っていそうだったが、彼のデバッグ力により無事 AC (1:04)
D に想定以上の時間を使っていたのが結構痛いな、と感じていた。
D2
a01sa01to が E の実装をしている最中に私は D に戻り、kAsA02 から「ある行（または列）を基準としたとき、他のすべての行は、その基準行と完全に一致するか、完全に反転したパターンになっていなければならない」という考察を聞き、納得していた。 各行・列で RLE を行い、端以外の要素の個数が全部一致していればそれが答えの候補となり、全部一致していなければ矛盾する。RLE 後の要素が二つしか無い時は一片の長さとしての候補が無いことになるので一意に定まらなさそう。
ここまで議論を重ねていたところ E を AC して合流してきた a01sa01to に進捗を伝え、実装を始めてもらう。比較的すぐに実装が終わりサンプルを試してみると、どうやら矛盾するケースで一意に定まる判定をしている。
一辺の長さの候補は RLE した時の端以外の要素で求められるので、端の要素を無視していたが、どうやら端の要素は候補にはならないが一片の長さの候補がある時にそれ以下かの判定はする必要があることに気づいた。これを追加すると、サンプルは無事に通り、他の怖いケースなどを少し生成して大丈夫そうであることを確認したのちに提出し、無事 AC (1:23)
時間がかかってしまったものの、他チームを順位表で見ていると比較的ペナが多そうなので、そこをノーペナで通せたのは非常に心強かった。
F
E を通した後に F を全員で読む。 私と kAsA02 が問題文の読解に躓いている中、a01sa01to が分かっていそうなので教えてもらう。 理解はしたが、A と B が何を動かすのかがごちゃごちゃになるので、問題文を整理して紙に書きつける。 実際にサンプルに対して実験をしていたところ、a01sa01to が a, b の文字数が一致していれば 1 文字当たり高々 100 回で挿入する操作が出来そうということに気づいた。 その考察を聞いて確かにとなり、実装は a01sa01to がもう頭の中である程度出来ていそうだったので、実装を任せる。 パッと G, H を見て、自分は G のサンプルの意味が良く理解できなかったので、kAsA02 に G に行ってもらい、自分は H に行くことにした。
少しして実装が出来たとのことで提出すると AC (1:53) ここでもう予選通過はしただろうとなり、残りの 1 時間を安心して戦うことができた。(結局、追加のACは取れなかったが)
G, H
自分は H の問題を見ていて、"((" と "))" があれば個数調整はできそうなことと、"(" を 1, ")" を -1 として、スタート ~ ゴールまでの最短距離での総和の偶奇で正しい括弧列が作成可能か判定ができそうなことに気づいたが、結局 から落ちる方法が分からず。 そこから進展の兆しが見えなかったので、G に合流することにした。
G に合流すると、進捗があったようで、「面 H1, H2 のある辺が平行であれば、その 2 辺の端点をつなげると四角形の平面を構成できるので良さそう、それ以外は三角形の面を構成しないと平面が構成できなさそう」とのこと。
確かにとなる。a01sa01to と kAsA02 はオイラーの多面体定理とか平面的グラフ (?) を考えていたが、あまり分からなかったので別方針で考える。しばらくして、平行かどうかは、2 つの多角形の各頂点について、ある点を始点とした角度の累積和を管理し、一致する箇所があるかで判定できそうだということ、また上限が になりそうだという考察をチームで共有した。
考察が進み、これを実装すればいけるのでは ? というところまでは言ったが、その時点で残り時間があと数分ほどに迫っていて間に合わないことが判明したので終了。
終了後
全体 40 位 + 学内 1 位を見て横浜進出を確信し、安堵しました。 また順位表をスクロールして見ると緑・茶・茶の後輩のチームが 5 完していて伸びしろがあっていいなと思いました。
終了後に私たちの大学から国内予選にでている 8 チームで打ち上げに行きました。 最近はサークルに顔を出す機会がほとんどないので、後輩や同期の近況について聞けて良い機会でした。
おわりに
ラストイヤーも無事進出することができてとても良かったです。
昨年は同じチームメンバーで横浜に進出できたものの、横浜では悔しい結果に終わりました。今年は昨年を大幅に上回る順位を出し、そして、あわよくば Playoff 進出を目指して頑張ります！