ICPC 2025 Yokohama 国内予選参加記 (await_inshi, Not_Leonian)

はじめに

ICPC 2025 Yokohama 国内予選に筑波大学から await_inshi で出て、結果は $6$ 完 $53$ 位でした。学内 $2$ 位で、選抜手順 $1$ の $39$ チーム目としてギリギリ通過することができました。

メンバー

Not_Leonian: 筆者。AtCoder の色は青。チーム内では数学と高度典型を担当することになっているが、国内予選では考察の補助と shibaken496 の実装ミスの検出くらいしかできることがない。横浜大会に向けて、自信を持って数学と高度典型の担当と言えるようにならなければ。
shibaken496: AtCoder の色は青。await_inshi の実装担当であり、チーム内で最も競技プログラミング歴が長く、最も強い。チーム内で院試の出願が最も遅く、本当に await_inshi になってしまった（開始には間に合ったので気にしていない）。
MoroMari: AtCoder の色は水。地頭が良いので多分競プロだけに本気を出せば余裕で青になれると思う。国内予選のような問題の考察は普通に頼れる。イーノック並にインターネット上で使用している名前が多い。

なお、チームの方針として、基本的に $3$ 人で同じ問題を考察し、shibaken496 の実装を常に $2$ 人で確認するというのがあります。これは、去年の敗退を教訓にしたものでもあり、去年の saehass の真似をしたものでもあります。もちろん最上位を狙う上では分業は必要だと思いますが、このチームで最上位を狙うためにはそもそも個人がもっと強くなる必要があり、それからだと考えています。

大会前

競技プログラミングを始めたタイミングや編入試験のタイミングなどの理由で、高専の $2$ 年間に ICPC に参加することができなかった私は、そのぶん ICPC に懸ける思いは強いです。そんな中で、私は去年の ICPC の数か月前に AtCoder のレートを $300$ 失い、ICPC の前に半分ほど戻したものの、青コーダーに戻るのは間に合いませんでした。去年の実装担当は私でしたが、C 問題でしょうもない実装ミスで時間をロスして早々に自信を失ってしまいました。チームメイトの片方に D 問題の実装を押しつけ、もう片方に E 問題の考察を押しつけた結果、その $2$ 人もミスをして $4$ 完という屈辱的な結果で敗退しました。

ラストイヤーの来年に向けて横浜大会に出て経験を積みたいことと、I_do_understand_the_danger_of_overflow_and_really_want_to_use_32bit_integer の解散で例年よりはチャンスがあることから、私は今年を勝負の年と決めていました。去年はチームの練習にはあまり参加していませんでしたが、それを反省して毎週練習したり、模擬国内予選に出たりしました。

模擬国内予選

A 問題

$3$ 分。少々面倒ですが、やって通りました。

B 問題

$10$ 分。私と MoroMari の両方が問題文を早く読みすぎて誤読し、危なかったですがやって通りました。

C 問題

$16$ 分。私がすぐに分母をはらうことを提案し、 $2$ 人もすぐに納得して書きました。前計算するかでちょっと議論にはなりましたが、そこまで苦労はしませんでした。

D 問題

$31$ 分。当たり方針を引くまでに時間がかかりました。私が開き括弧を使って $1$ 文字ずつ決めていけるという方針を提案し、MoroMari が使う開き括弧をスタックで持てばいいと補足しました。丁寧丁寧丁寧な実装後の確認により、自信を持って提出し、通りました。

E 問題

$124$ 分。チームの事前の練習では、 $\Omega(|S| ^ 2)$ の構文解析ばかり書いていました。まず、 $o(|S| ^ 2)$ の構文解析をどう書くかということで詰まってしまいました。

MoroMari が構文解析後の木を提案し、それをもとに shibaken496 が実装を始めましたが、私は疲れていたため途中まで $2$ 人が何を書こうとしているのかわからず、おそらくその方針では駄目そうな気がするという直感を主張できずにいました。やはりバグっており、ブレークポイントを打ってのデバッグを何回もすることでやっと直せました。

相当沼ってしまったので、本番ではチーム全体で全員がやることを理解してから書こうという話になり、私個人としてもこれを模擬の一番の反省点として心に刻みました。また、shibaken496 は模擬の後、本番までに構文解析を練習してくれました。ありがとう。

その後

数学担当の私がいる以上、H 問題が一番マシなのではないかという話になり、H 問題を考えさせてもらいました。ただし、残り $1$ 時間弱では詰め切れず、 $5$ 完で終了しました。

学内 $1$ 位であったものの、全てのチームが出ているわけではないのであまり参考にはならないと冷静に考えていました。

本番

A 問題

$2$ 分。愚直に計算できるので愚直に計算しました。

B 問題

$8$ 分。 MoroMari が正当ではありそうだが面倒そうな方針を提案していたので、「testt」「testst」「testest」… と構築して確認すればよいと提案しました。これは似た問題か全く同じ問題を知っていました。 shibaken496 が「ttest」「tetest」「testest」… のほうで実装しており、確かにそのほうが実装は楽だなぁと感心しました。

C 問題

$18$ 分。 $1$ 人では絶対にやりたくない問題ですね。 $3$ 人で協力して全ての罠を見抜き、一発で通すことができました。

D 問題

$1$ 時間 $23$ 分。見ただけでやりたくなくなる問題ですね。

先にありえる周期を特定する方針を自分が提案してしまい、その方針で考察を終えた後、「その実装ではこのケースで困る」という指摘をしまくるマッチポンプをしてしまいました。結局、コードを一旦全削除して、先に矛盾しているケースを順に弾き落とす方針に変えて通すことができました。

E 問題

$2$ 時間 $14$ 分。この問題のムーブはチームとしての明確な反省点でした。

去年、E 問題で嘘を書いて敗退した私たちは、貪欲の正当性に過剰に敏感になっており、本当に貪欲なのかを必要以上に吟味していました。 $1$ 人が嘘反例を出して、それを残り $2$ 人で否定するといったことも何回もありました。結局、貪欲で合っているだろうと書いて通りました。結果的には貪欲でなかった場合のペナルティ $20$ 分と考察のやり直しと実装のやり直しと同じ程度の時間を消費してしまい、それならさっさと書いてしまえばよかったということになりました。

また、D より E のほうを先にやればよかったという反省点もなくはないですが、ここまで E で悩んでいるとあまり変わらないでしょう。

F 問題

$2$ 時間 $53$ 分。本当に F 問題を通せたのは大きかった。

正直、去年の saehass が $5$ 完で突破していたことと、模擬で $5$ 完だったことから、解けたらラッキー程度で見始めました。チームメイト $2$ 人が結構わかりそうな感じで取り組んでいた中、私が「 $N\leq 100$ に対して $10000$ 回以内だから、自明な No 以外全部 Yes なんじゃないの？」と無根拠で発しました。特に MoroMari は疑っていたものの、最終的には MoroMari が楽な方針を考えついてくれました。自分はその方針を実装するうえでこうすると楽になりそうといった点を補足し、なんとか間に合わせて一発で通すことができました。

個人戦だったら絶対に焦って通せなかったと思いますが、チームメイト $2$ 人の「この残り時間なら間に合う」という絶対的な自信に身を任せることができました。

おわりに

思ったよりギリギリで肝を冷やしましたが、チームで一丸となって闘ったおかげで通過できました。横浜大会も頑張りたいです。