概要

一直線上に並ぶ \(N\) 軒の家すべてを、\(M\) 種類の街灯を使って照らすための最小費用を求める問題です。各街灯は任意の実数座標に設置でき、設置位置から半径 \(R_j\) 以内の家を照らします。

考察

重要な気づき①：家をソートして区間被覆問題に帰着

家の座標をソートすると、1 基の街灯が照らす家は連続する区間になります。なぜなら、街灯が照らす範囲は数直線上の連続区間 \([p - R_j, p + R_j]\) であり、ソート済みの家のうち照らされるものは必ず連続するからです。

重要な気づき②：貪欲な配置

家 \(i\)（0-indexed）から右方向にできるだけ多くの家を照らしたいとき、街灯を \(X_i + R_j\) の位置に設置するのが最適です。このとき： - 左端：\(X_i + R_j - R_j = X_i\)（家 \(i\) をちょうど照らせる） - 右端：\(X_i + R_j + R_j = X_i + 2R_j\)

つまり、座標が \(X_i + 2R_j\) 以下の家はすべて照らされます。

素朴なアプローチの問題

各家 \(i\) に対して「どの街灯をどこに置いてこの家を照らすか」を全探索すると、状態が爆発してしまいます。しかし、上記の貪欲な配置を使えば、効率的な DP が構築できます。

アルゴリズム

DP の定義： \(dp[i]\) = ソート後の最初の \(i\) 軒の家（家 \(0, 1, \ldots, i-1\)）をすべて照らすための最小費用

初期値： \(dp[0] = 0\)（まだどの家も照らす必要がない状態）

遷移： 状態 \(i\)（家 \(0\) ～ \(i-1\) まで照らし済み）から、次に家 \(i\) を照らす街灯を選ぶ： - 種類 \(j\) の街灯を \(X_i + R_j\) に設置すると、座標 \(\leq X_i + 2R_j\) のすべての家が照らされる - 二分探索で、照らされる最後の家の次のインデックス \(\text{nxt}\) を求める - \(dp[\text{nxt}] = \min(dp[\text{nxt}],\ dp[i] + C_j)\)

答え： \(dp[N]\)

具体例

家が座標 \([1, 3, 7, 10]\) にあり、半径 \(2\)、費用 \(5\) の街灯があるとします。 - \(dp[0] = 0\) から出発し、家 \(0\)（座標 \(1\)）を照らす - 街灯を \(1 + 2 = 3\) に設置 → 座標 \(\leq 1 + 4 = 5\) の家を照らす → 家 \(0, 1\) が照らされる - \(dp[2] = \min(dp[2], 0 + 5) = 5\)

計算量

• 時間計算量: \(O(N \log N + NM \log N)\)
  • ソートに \(O(N \log N)\)
  • DP の遷移が \(N \times M\) 回、各遷移で二分探索 \(O(\log N)\)
• 空間計算量: \(O(N + M)\)

\(N, M \leq 3000\) なので、\(NM = 9 \times 10^6\) 回の遷移で十分高速です。

実装のポイント

• 家の座標をソートしてから DP を行うことが必須です。ソートしないと「連続する家を1基で照らす」という構造が使えません。

• 二分探索（bisect_right）を使って、\(X_i + 2R_j\) 以下の座標を持つ家の個数を高速に求めます。

• dp[i] == INF の状態からは遷移しないようにすることで、無駄な計算を省きます。

• 答えが \(64\) ビット整数に収まることが保証されていますが、Python では整数のオーバーフローを気にする必要はありません。

  ソースコード

import sys
from bisect import bisect_right

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    X = []
    for i in range(N):
        X.append(int(input_data[idx])); idx += 1
    
    lights = []
    for j in range(M):
        R = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        lights.append((R, C))
    
    X.sort()
    
    # Precompute: for each light type j, and for each starting house i,
    # how many consecutive houses (starting from i) can one light of type j cover?
    # A light of type j with radius R can cover all houses in a contiguous range of width 2*R.
    # If we want to cover houses starting from house i, the optimal placement covers
    # houses from X[i] to X[i] + 2*R. So we find the rightmost house with coordinate <= X[i] + 2*R.
    
    # DP: dp[i] = minimum cost to illuminate houses 0..i-1 (first i houses)
    # dp[0] = 0
    # dp[i] = min over all ways to cover a suffix ending at house i-1
    # For each light type j, if we place it to cover houses starting at house k,
    # it covers houses k..m-1 where m is the furthest house reachable.
    # dp[m] = min(dp[m], dp[k] + C_j)
    
    # Equivalently: dp[i] = min over j, over valid k such that one light of type j
    # can cover houses k..i-1, of dp[k] + C_j
    # For light type j covering houses k..i-1: need X[i-1] - X[k] <= 2*R_j
    # So k >= leftmost index where X[k] >= X[i-1] - 2*R_j
    
    # But this is O(N*M*N) naively. We need to be smarter.
    
    # Alternative approach: dp[i] = min cost to cover houses 0..i-1
    # Transition: for each light type j, from state i (houses 0..i-1 covered),
    # place a light of type j starting to cover house i. It covers houses i..nxt_j(i)-1
    # where nxt_j(i) = number of houses with coordinate <= X[i] + 2*R_j.
    # dp[nxt_j(i)] = min(dp[nxt_j(i)], dp[i] + C_j)
    
    # This is O(N*M) which is 2000*2000 = 4M, acceptable.
    
    INF = float('inf')
    dp = [INF] * (N + 1)
    dp[0] = 0
    
    # Precompute for each (i, j): if we start covering from house i with light j,
    # how far do we get?
    # The light covers [X[i] - R_j, X[i] + R_j] optimally placed at X[i] + R_j (or wherever).
    # Actually, we place the light at position p, covering [p - R_j, p + R_j].
    # We need house i to be covered: |X[i] - p| <= R_j, so p >= X[i] - R_j.
    # To maximize coverage to the right, set p = X[i] + R_j.
    # Then the light covers houses with coordinate <= X[i] + 2*R_j.
    
    for i in range(N):
        if dp[i] == INF:
            continue
        for R, C in lights:
            # Place light to cover from house i onwards as far as possible
            max_coord = X[i] + 2 * R
            # Find number of houses with coordinate <= max_coord
            nxt = bisect_right(X, max_coord)
            if dp[nxt] > dp[i] + C:
                dp[nxt] = dp[i] + C
    
    print(dp[N])

solve()

---

この解説は claude4.6opus-thinking によって生成されました。