充電器をどこに置く?

EVが増え、高速道路の各サービスエリアで充電待ちが長くなっています。一直線上にサービスエリアが複数あり、予算の都合で ちょうどC箇所だけ に充電器を設置できるとしたら——どこに置くべきでしょう?

ポイントはこれです。充電器が一箇所に偏ると、遠い区間は充電が不便になります。だから「最も近い2つの充電器の距離」を できるだけ大きく するのが目標です。

例: サービスエリアが 3, 6, 12, 17, 25, 30(km)にあり、充電器3個なら? 答えは13km。 (3・17・30に置くと間隔14, 13 → 最小13)

どう approach する? (核心アイデア)

最初は途方に暮れます。「どのエリアを選ぶか」を直接決めようとすると組み合わせが爆発するからです。

発想の転換 — 位置を選ぶのではなく、答え(最小距離D)を先に仮定します。

•「充電器間の最小距離が D以上 になるようにC個置けるか?」→ これは 貪欲法で素早く判定できます(先頭に必ず設置し、直前の設置点からD以上離れた所ごとに設置)。
•Dが小さければ置きやすく(可能)、大きければ難しい(不可能)。つまり Dについて単調です。
•単調なら? 二分探索 で「可能な最大のD」を見つけられます。

これが パラメトリックサーチ ——*答えそのものを二分探索する* 手法です。ソート済み配列で値を探すのではなく、答えの候補範囲を絞っていくのです。

多くの人は「二分探索=ソート済み配列で値を探す」とだけ学びます。だから *「答えを二分探索する」* 発想は最初なかなか出てきません。

でも一度 目で見れば 一気に腑に落ちます。

1. 候補距離Dを1つ決める

2. そのDで先頭から充電器を1つずつ置いてみる(貪欲法)

3. 置けた数が十分なら Dを上げ、足りなければ下げる

4. 範囲が狭まり答えに収束する

この流れを ステップごとのアニメーション で追うと、「*だから* 二分探索なのか」が一瞬で分かります。

サービスエリアが数直線上に並び、候補距離Dが狭まり、充電器が貪欲に1つずつ置かれる 全工程 をステップ別の可視化で用意しました。変数の変化(lo・mid・hi、設置数)まで一目で分かります。

パラメトリックサーチは「ルーター設置」「木を切る」「予算配分」など無数の変形でコーディングテストに登場します。一度原理を目で覚えれば、どんな姿で出ても解けます。