概要

住民 \(i\) が電波を受信できる基地局の位置は区間 \([X_i - R_i, X_i + R_i]\) で表されます。基地局の設置候補を各区間の右端点に限定し、「各区間を最初にカバーする基地局でのみカウントする」という方針を取ることで、2次元いもす法による前計算と動的計画法（DP）を組み合わせて \(O(K N^2)\) で解くことができます。

考察

1. 問題の区間への言い換え

住民 \(i\) が座標 \(P\) にある基地局から電波を受信できる条件は \(|X_i - P| \le R_i\) です。 これは、基地局の座標 \(P\) が閉区間 \([X_i - R_i, X_i + R_i]\) に含まれていることと同値です。 以下では \(L_i = X_i - R_i,\ R'_i = X_i + R_i\) とおきます。

2. 基地局の設置候補を絞り込む

基地局は実数上のどこにでも設置できますが、最適解において基地局の位置はある区間の右端点 \(R'_i\) に一致させて良いことが分かります。 なぜなら、ある基地局を右にスライドさせたとき、カバーできなくなる住民が現れるのは「その住民の区間の右端点を通り過ぎた瞬間」だけだからです。したがって、カバーする住民の集合を変えずに、基地局を右端点までスライドさせることができます。

これにより、基地局の設置座標の候補は高々 \(N\) 個の \(\{R'_1, R'_2, \dots, R'_N\}\) に絞られます。 これらの重複を除いて昇順にソートしたものを \(c_1 < c_2 < \dots < c_M\) とします（\(M \le N\)）。

3. 重複カウントを防ぐルール付け

複数の基地局が同じ区間をカバーする場合、その住民を \(1\) 回だけカウントする必要があります。 基地局を左から順に選んでいくとき、各区間を「その区間をカバーする最も左の基地局」に所属させると考えます。

直前に選んだ基地局を \(c_u\)、今回選ぶ基地局を \(c_v\) (\(u < v\)) としたとき、基地局 \(c_v\) で初めてカバーされる区間 \(i\) の条件は次のようになります： - 直前の基地局 \(c_u\)（およびそれより左の基地局）ではカバーされない：\(c_u < L_i\) - 今回の基地局 \(c_v\) でカバーされる：\(L_i \le c_v \le R'_i\)

まとめると、\(c_u < L_i \le c_v \le R'_i\) を満たす区間が、直前の基地局を \(c_u\) としたときに \(c_v\) を選ぶことで新たに得られるスコアとなります。 なお、最初に選ぶ基地局（1個目）については直前の基地局が存在しないため、番兵として \(c_0 = -\infty\) を用意すれば一括して同じ式で扱えます。

アルゴリズム

1. 候補点の抽出: 各住民の区間 \([L_i, R'_i]\) を求め、\(R'_i\) のユニークな値をソートして \(c_1 < \dots < c_M\) とします。番兵 \(c_0 = -\infty\) も追加します。基地局の個数 \(K\) が \(M\) より大きい場合は、同じ位置に置くか無駄な基地局になるだけなので \(K \leftarrow \min(K, M)\) とします。

2. コストの前計算（2次元いもす法）: 各ペア \((u, v)\) に対し、\(c_u < L_i \le c_v \le R'_i\) を満たす区間数を cost[u][v] とします。 1つの区間 \([L_i, R'_i]\) が寄与する \((u, v)\) の範囲を考えると、

   • \(v\) の条件: \(L_i \le c_v \le R'_i\) を満たす \(v\) の範囲は二分探索で \([v_{\text{start}}, v_{\text{end}}]\) と求まる。
   • \(u\) の条件: \(c_u < L_i\) を満たす最大の \(u\) は \(u_{\text{max}} = v_{\text{start}} - 1\) であり、\(0 \le u \le u_{\text{max}}\) となる。

これは \((u, v)\) 平面上の矩形領域 \([0, u_{\text{max}}] \times [v_{\text{start}}, v_{\text{end}}]\) に対する \(+1\) 加算となります。 2次元いもす法を用いることで、すべての区間に対する加算を \(O(N \log M + M^2)\) で行えます。

1. 動的計画法 (DP):
   • dp[t][v]: 基地局を \(t\) 個設置し、最後に設置した基地局が \(c_v\) であるときの、電波を受信できる住民の最大数

初期値: - dp[1][v] = cost[0][v] （\(1 \le v \le M\)）

遷移: \(t = 2, 3, \dots, K\) について、 $\(dp[t][v] = \max_{1 \le u < v} \{ dp[t-1][u] + \text{cost}[u][v] \}\)$

答え: 各ステップにおいて \(\max_{1 \le v \le M} dp[t][v]\) の最大値が答えとなります。

計算量

• 時間計算量:
  • 座標の抽出・ソート: \(O(N \log N)\)
  • 2次元いもす法による cost の前計算: \(O(N \log M + M^2)\)
  • DPの更新: \(K\) 回のステップそれぞれで \(v\) を \(1 \dots M\)、その中で \(u\) を \(1 \dots v-1\) 探索するため、\(O(K M^2)\)
  • 全体として \(O(K M^2) \le O(K N^2)\) です。\(N \le 250\) より、\(K N^2 \le 250^3 \approx 1.56 \times 10^7\) となり、制限時間内に十分余裕を持って実行可能です。
• 空間計算量:
  • cost 配列および DP テーブルの保持に \(O(M^2) \le O(N^2)\) のメモリを消費します。\(N \le 250\) ではごくわずかです。

実装のポイント

• 2次元いもす法: 素直に cost[u][v] を各区間ごとにループで求めると \(O(N M^2)\) かかりますが、矩形加算であることを利用していもす法を用いることで \(O(N \log M + M^2)\) に高速化できます。

• キャッシュ効率の改善: DPの遷移式 dp[u] + cost[u][v] では \(v\) を固定して \(u\) を動かすため、2次元配列 cost[u][v] の第1添字が変化します。Python などの言語ではメモリの局所性を高めるために cost を転置して cost_T[v][u] = cost[u][v] としておくと、内側ループのアクセスが連続になり実行時間が大幅に短縮されます。

  ソースコード

import sys
from bisect import bisect_left, bisect_right


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    K = int(input_data[1])

    intervals = []
    idx = 2
    R_primes = []
    for _ in range(N):
        x = int(input_data[idx])
        r = int(input_data[idx + 1])
        idx += 2
        L = x - r
        R = x + r
        intervals.append((L, R))
        R_primes.append(R)

    c_unique = sorted(list(set(R_primes)))
    M = len(c_unique)
    K = min(K, M)

    c = [-10**18] + c_unique

    # 2次元いもす法で cost[u][v] を前計算
    # cost[u][v]: c_u < L_i <= c_v <= R_i を満たす区間の数 (0 <= u < v <= M)
    diff = [[0] * (M + 2) for _ in range(M + 2)]

    for L, R in intervals:
        v_start = bisect_left(c, L)
        if v_start > M:
            continue
        v_end = bisect_right(c, R) - 1
        if v_start > v_end:
            continue
        u_max = v_start - 1

        diff[0][v_start] += 1
        diff[0][v_end + 1] -= 1
        diff[u_max + 1][v_start] -= 1
        diff[u_max + 1][v_end + 1] += 1

    for u in range(M + 1):
        row = diff[u]
        for v in range(1, M + 1):
            row[v] += row[v - 1]

    for u in range(1, M + 1):
        row_prev = diff[u - 1]
        row_curr = diff[u]
        for v in range(M + 1):
            row_curr[v] += row_prev[v]

    cost = diff

    # 転置してメモリアクセスを高速化
    cost_T = [[cost[u][v] for u in range(v)] for v in range(M + 1)]

    dp = [cost[0][v] for v in range(M + 1)]
    ans = max(dp[1:])

    for t in range(2, K + 1):
        next_dp = [0] * (M + 1)
        for v in range(1, M + 1):
            c_v = cost_T[v]
            m = 0
            for u in range(1, v):
                val = dp[u] + c_v[u]
                if val > m:
                    m = val
            next_dp[v] = m
        dp = next_dp
        cur_max = max(dp[1:])
        if cur_max > ans:
            ans = cur_max

    print(ans)


if __name__ == "__main__":
    main()

---

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