概要

家の座標を昇順に並べ、「左端のまだ照らされていない家」から始めて街灯を置くときに最適な遷移だけを考えることで、動的計画法で最小費用を求めます。

考察

重要な気づき

家を座標順に \(x_0 < x_1 < \dots < x_{N-1}\) とします。
いま左端の未被覆の家が \(x_i\) だとして、半径 \(R\) の街灯を「\(x_i\) を照らすように」置くとき、右方向にできるだけ多くの家を照らしたいなら、街灯の中心を \(x_i + R\) に置くのが最適です。

• 中心を \(p\) に置くと照らす区間は \([p-R,\; p+R]\)
• \(x_i\) を照らすには \(p \in [x_i-R,\; x_i+R]\)
• 右端 \(p+R\) を最大化するには \(p=x_i+R\)
• よって照らせる区間は \([x_i,\; x_i+2R]\)

つまり、「次に照らせる家の範囲」は \(x_i\) と街灯種類だけで一意に決まります。

素朴解が厳しい理由

• 「街灯をどこに置くか」は実数座標なので探索空間が無限
• 各状態で二分探索をすると \(O(NM\log N)\) になり、\(N,M\le 3000\) では重くなりがち

どう解決するか

1. 実数の位置決め問題を、「左端の未被覆の家 \(x_i\) から右へどこまで届くか」だけの問題に落とす（上の気づき）。
2. 同じ到達距離 \(2R\) の街灯は 最安コストだけ残す。
3. さらに、ある街灯 \((L, C)\) に対し \(L' \ge L\) かつ \(C' \le C\) な街灯が存在するなら、\((L,C)\) は常に劣るので削除（支配される種類の除去）。
4. DP 遷移で必要な「\(x_i+L\) 以下の最後の家」を、種類ごとにポインタを動かして高速化（各種類で右端が単調増加）。

ここで \(L=2R\) とおくと、到達右端は \(x_i+L\) となり整数のまま扱えます。

アルゴリズム

1. 前処理（街灯種類の圧縮・不要削除）

• 各街灯について \(L=2R\) を計算し、同じ \(L\) の中では最小の \(C\) のみ残す。
• 残った \((L,C)\) を \(L\) 昇順に並べる。
• 右から見ていき、これまでの最小コスト minC より安いものだけを残す。
  • 右側（より大きい \(L\)）で安いものがあるなら、左側は使う意味がないため。

2. DP（家を左から順にカバー）

• dp[i] = 「左から \(i\) 軒（\(x_0 \sim x_{i-1}\)）をすべて照らす最小費用」
• 初期値 dp[0]=0、それ以外は INF
• 状態 \(i\)（次に照らすべき家が \(x_i\)）から、各街灯種類 \((L,C)\) を 1 基置く：
  • その街灯は区間 \([x_i,\; x_i+L]\) を照らす（上の考察）
  • よって、\(x_k \le x_i+L\) を満たす最大の \(k\) まで一気にカバーできる
  • 次状態は dp[k] = min(dp[k], dp[i] + C)

到達位置 \(k\) の求め方（ポインタ）

各種類ごとに「右端 \(x_i+L\) 以下の家の個数」を指すポインタ r[j] を持ちます。
\(i\) が増えると \(x_i\) も増えるので、\(x_i+L\) も単調増加し、r[j] は後ろにしか動きません。
よって while で進めるだけで合計の移動回数は高々 \(N\) 回/種類になります。

最終的な答えは dp[N] です。

計算量

• 時間計算量:
  
  • 家のソート \(O(N\log N)\)
    
  • 街灯種類の整理（ソート） \(O(M\log M)\)
    
  • DP 部分 \(O(NK)\)（\(K\) は支配削除後の種類数で \(K\le M\)）
  • よって全体で \(O(N\log N + M\log M + NK)\)
• 空間計算量: \(O(N+K)\)

実装のポイント

• \(L=2R\) として「右端 \(x_i+L\)」を整数で扱う（浮動小数は不要）。

• 同じ \(L\) の街灯は 最安値だけ残す（辞書 best_by_L）。

• 「大きい範囲で安い」街灯があるとき小さい範囲の街灯は不要なので、右からの走査で支配削除する。

• DP で毎回二分探索せず、種類ごとのポインタ r[j] を使って高速化する。

• 答えは \(10^9\) オーダーが累積するので、INF は十分大きい値（例：\(10^{30}\)）にする。

  ソースコード

import sys

def main() -> None:
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    M = int(next(it))
    xs = [int(next(it)) for _ in range(N)]
    xs.sort()

    best_by_L = {}
    for _ in range(M):
        R = int(next(it))
        C = int(next(it))
        L = R << 1
        prev = best_by_L.get(L)
        if prev is None or C < prev:
            best_by_L[L] = C

    items = sorted(best_by_L.items())  # (L, C) ascending by L

    # Remove dominated types: if there exists L' >= L with cost <= C, then (L,C) is useless.
    filtered = []
    minC = 10**30
    for L, C in reversed(items):
        if C < minC:
            filtered.append((L, C))
            minC = C
    filtered.reverse()

    Ls = [p[0] for p in filtered]
    Cs = [p[1] for p in filtered]
    K = len(Ls)

    INF = 10**30
    dp = [INF] * (N + 1)
    dp[0] = 0

    r = [0] * K  # pointers for each type (upper_bound index)

    xs_local = xs
    dp_local = dp
    N_local = N
    for i in range(N_local):
        base = dp_local[i]
        if base == INF:
            continue
        xi = xs_local[i]
        for j in range(K):
            t = xi + Ls[j]
            rj = r[j]
            while rj < N_local and xs_local[rj] <= t:
                rj += 1
            r[j] = rj
            cand = base + Cs[j]
            if cand < dp_local[rj]:
                dp_local[rj] = cand

    print(dp_local[N_local])

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。