ICPC2026 国内予選参加記

2026/07/04

はじめに

私です。

7月3日に開催されたICPC国内予選に、チーム WaSanBon (Twil3akine、Caffeineholic、Akagi_Shrine) で参加しました。

配られたカードのうち、大富豪で一番強いカードを出力する問題です。

カードの数字を $x$ として、強さの比較に使う値 $f(x)$ を次のように定めました。

f(x) = \begin{cases} x + 13 & (x \in \{1, 2\}) \\ x & (3 \le x \le 13) \end{cases}

$f(x)$ が最大になるカードを選び、元の数字に戻して出力します。実装では、最大値が $14$ 以上なら $13$ を引き、そうでなければそのまま出力しました。

コンテスト後に「 $1$ または $2$ が含まれていれば強いほうを出し、どちらもなければ最大値を出す」という解法を聞いて、賢いなぁ…と感じました。

自動販売機を置くと、設置位置から距離 $d$ 以内にある扉をカバーできます。すべての扉をカバーするために必要な自動販売機の最小台数を求める問題です。

最初は「必ず各扉の間に自動販売機がなければならない」と誤読しており、若干のタイムロスをしてしまいました。

扉の位置を昇順に $x_0, x_1, \ldots, x_{n-1}$ とします。まだカバーされていない最も左の扉を $x_i$ とすると、自動販売機を $x_i+d$ に置くことで、右端 $x_i+2d$ までカバーできます。

したがって、次の貪欲法で求められます。

誤読に気付いたあとは、すぐに正しい方針へ進めたのでよかったです。

持ち前の語弱をここで遺憾なく発揮してしまい、問題文を読んでも全然分かりませんでした。頭をひねって考えた結果、「何か凸性が関係ありそうだなぁ」というところで思考をロックしてしまいました。

終了後にほかのチームの子から話を聞くと、「上から見て、壁にぶつかるまで各マスの水をなくす」という処理を左右から1回ずつ行うだけでよかったらしく、本当に悲しくなりました。

これは完全に私の考察ミスです。チームのみんなに申し訳ないです。

難しすぎて、今年の重実装枠はCに来たのかと思いました。実態は私の考察ミスです。

私はこの問題にほとんど関与していませんが、考察はほぼ合っていたようです。C問題の考察をスムーズに終えられていたら、これも解けていたのではないかと思います…。

内容に触れると、群数列のような構造になっていて、 $s^2$ と $k$ の大小関係によって場合分けが生じるようです。

考えていると、どうしても貪欲法でよいように思えてきます。

瓶全体の集合を $U$ 、ジェム付きの瓶の集合を $G$ とします。ジェムが付いていない瓶の集合は、補集合 $U \setminus G$ です。また、ジェム付きの瓶の最小コストを $c_{\min}$ とします。

コンテスト中は、次のように場合分けして考えました。

「それ以外」のケースをもう少し詰めていれば正解できたそうで、ここに時間を割けなかったことが本当に悔いになっています。

BFSをすればよいのでは、と思ったのですが、 $n \le 10^9$ の正方形グリッドなので撤退しました。

何か絶対に賢い方法があるんだろうなぁ、と思うんですけどね…。

G問題以降は、問題を見ることすらできていません。

いつの間にか、次はICPCに参加できる最後の年になってしまいました。

来年はもうM1です。来年は横浜に行きたいです。この1年は真面目に頑張ろうと思います。

ちゃんとチーム練習とかね…。