概要

この問題は、数直線上に配置された \(N\) 軒の家を、カバー範囲 \(2R_j\)、コスト \(C_j\) の街灯をいくつか使ってすべてカバーする際にかかる費用の最小値を求める問題です。 街灯は設置位置を自由に選ぶことができ、同じ種類の街灯を何回でも使用できます。

---

考察

1. 街灯の性質の整理

街灯 \(j\) をある座標に設置したとき、その街灯がカバーできる範囲の長さ（直径）は \(D_j = 2R_j\) となります。 したがって、各街灯は「長さ \(D_j\) の区間をコスト \(C_j\) でカバーできるアイテム」とみなせます。

ここで、以下の2つの街灯 \(A, B\) を比較してみましょう。 - 街灯 \(A\): カバー範囲 \(D_A\)、コスト \(C_A\) - 街灯 \(B\): カバー範囲 \(D_B\)、コスト \(C_B\)

もし \(D_A \ge D_B\) かつ \(C_A \le C_B\) であるなら、街灯 \(B\) を使うメリットは一切ありません（街灯 \(A\) の方が広くカバーできてコストも安いため）。 このような「無駄な街灯」を事前に取り除く（フィルタリングする）ことで、残った街灯のリストを「カバー範囲 \(D\) が広くなるほど、コスト \(C\) も高くなる」という綺麗な単調増加の関係に整理することができます。

2. 動的計画法 (DP) の適用

家の座標を昇順にソートして \(X_1 < X_2 < \dots < X_N\) とします。 左側から順番に家をカバーしていくことを考え、次のようなDP（動的計画法）を定義します。

• \(DP[i]\) : 左から \(i\) 軒目の家（\(X_i\)）までをすべてカバーするために必要な最小コスト

\(DP[i]\) を求めるために、最後に置く街灯がどの範囲をカバーするかを考えます。 最後に置く街灯が、右端の家 \(X_i\) をカバーし、さらに左側にある家 \(X_{j+1}\) までをまとめてカバーすると仮定します（\(0 \le j < i\)）。

この街灯がカバーしなければならない区間の長さは \(d = X_i - X_{j+1}\) です。 街灯は実数座標に自由に設置できるため、右端を \(X_i\) にぴったり合わせて設置すれば、左側は \(X_i - D\) までカバーできます。したがって、カバー範囲 \(D \ge d\) を満たす街灯の中で最もコストが安いものを選べばよいことになります。

このときの遷移式は以下のようになります。 $\(DP[i] = \min_{0 \le j < i} \{ DP[j] + (\text{長さ } X_i - X_{j+1} \text{ 以上をカバーできる最小の街灯コスト}) \}\)$

3. 尺取り法による高速化

各 \(i\) に対してすべての \(j\) (\(i-1\) から \(0\) まで減少) を試す際、必要なカバー長さ \(d = X_i - X_{j+1}\) は \(j\) が小さくなるにつれて単調増加します。

街灯リストをカバー範囲 \(D\) の昇順に並べておくと、必要なカバー範囲 \(d\) が大きくなるにつれて、条件 \(D_k \ge d\) を満たす最小の街灯インデックス \(k\) も単調増加（右に移動）します。 そのため、内側のループで \(j\) を減らしていく際、街灯のインデックス \(k\) を毎回 \(0\) から探し直す必要はなく、前回の \(k\) の位置から進めるだけで済みます（尺取り法の要領）。これにより、遷移を高速に行うことができます。

---

アルゴリズム

1. 初期化とソート:

   • 家の座標 \(X\) を昇順にソートします。
   • 各街灯の有効カバー範囲を \(D_j = 2R_j\) とします。

2. 街灯のフィルタリング:

   • 街灯を「カバー範囲 \(D\) の降順、コスト \(C\) の昇順」でソートします。
   • 左から順に見ていき、これまでの最小コストを更新するものだけを抽出します。
   • 抽出した街灯リストを反転させることで、\(D\) も \(C\) も昇順に並んだ無駄のない街灯リスト filtered を得ます。

3. DPの遷移:

   • \(DP\) 配列をサイズ \(N+1\) で用意し、初期値は十分大きな値（\(\infty\)）、\(DP[0] = 0\) とします。
   • \(i\) を \(1\) から \(N\) まで進めます。
     • 街灯リストのポインタ \(k = 0\) とします。
     • \(j\) を \(i-1\) から \(0\) まで逆順（デクリメント）にループします。
     • 必要な長さ \(d = X_{i-1} - X_j\) を計算します（0-indexedのため、家 \(i\) は X[i-1]、家 \(j+1\) は X[j] に対応します）。
     • \(D_k < d\) である限り、ポインタ \(k\) を進めます。
     • もし \(k\) が街灯リストのサイズを超えたら、それ以上長い区間をカバーできる街灯は存在しないため、内側ループを打ち切ります。
     • \(DP[i] = \min(DP[i], DP[j] + C_k)\) により値を更新します。

4. 出力:

   • \(DP[N]\) がすべての家をカバーする最小コストになります。

---

計算量

• 時間計算量: \(O(N^2 + M \log M)\)

  • 家のソートに \(O(N \log N)\) かかります。
  • 街灯のソートとフィルタリングに \(O(M \log M)\) かかります。
  • DPの計算において、外側ループは \(N\) 回、内側ループは \(N\) 回まわります。内側ループの中でポインタ \(k\) は最大でも \(M\) までしか増加しないため、DP全体の遷移にかかる時間は \(O(N^2 + M)\) です。
  • したがって、全体の時間計算量は \(O(N^2 + M \log M)\) となり、制限時間内に十分間に合います。

• 空間計算量: \(O(N + M)\)

  • DPテーブルのサイズが \(O(N)\)、フィルタリング後の街灯リストのサイズが最大で \(O(M)\) となるため、メモリ使用量は非常に小さく抑えられます。

---

実装のポイント

• 街灯のフィルタリング処理: この処理を行うことで、街灯の「カバー範囲 \(D\)」と「コスト \(C\)」に綺麗な単調性が生まれ、二分探索や尺取り法が適用可能になります。競プロにおいて非常に強力な典型テクニックの一つです。

• インデックスの対応: コード中では 0-indexed で実装されているため、家 \(i\)（1-indexed）が X[i-1] に対応している点に注意してください。家 \(j+1\) から \(i\) までの距離は X[i-1] - X[j] と表されます。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    M = int(data[1])

    X = [int(x) for x in data[2 : 2 + N]]
    X.sort()

    lights = []
    idx = 2 + N
    for _ in range(M):
        r = int(data[idx])
        c = int(data[idx + 1])
        lights.append((2 * r, c))
        idx += 2

    # 街灯のフィルタリング
    # カバー範囲Dが広いのにコストCが高いものは不要。
    # Dの降順、Cの昇順でソートし、これまでの最小コストを更新するものだけを残す。
    lights.sort(key=lambda x: (-x[0], x[1]))
    filtered = []
    min_c = float("inf")
    for d, c in lights:
        if c < min_c:
            filtered.append((d, c))
            min_c = c
    filtered.reverse()  # Dの昇順にする

    D_list = [item[0] for item in filtered]
    C_list = [item[1] for item in filtered]
    K = len(filtered)

    INF = 10**18
    DP = [INF] * (N + 1)
    DP[0] = 0

    for i in range(1, N + 1):
        xi = X[i - 1]
        k = 0
        dp_i = INF
        for j in range(i - 1, -1, -1):
            d = xi - X[j]
            while k < K and D_list[k] < d:
                k += 1
            if k == K:
                break
            val = DP[j] + C_list[k]
            if val < dp_i:
                dp_i = val
        DP[i] = dp_i

    print(DP[N])


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。