概要

各住民 \(i\) が電波を受信できる範囲を区間 \([X_i - R_i, X_i + R_i]\) とみなすと、本問題は「数直線上に \(K\) 個の点を選び、選んだ点によって被覆される区間の数を最大化する問題」と言い換えることができます。

基地局を置くべき最適な座標が各区間の右端に限定できること、および各区間を「最初に被覆する基地局」に割り当てることで重複を防げることに着目すると、動的計画法（DP）を用いて \(O(N^3 + K N^2)\) で効率的に解くことができます。

---

考察

1. 問題の言い換え

住民 \(i\) が座標 \(P\) にある基地局から電波を受信できる条件は、 $\(|X_i - P| \le R_i \iff X_i - R_i \le P \le X_i + R_i\)\( です。区間の左端を \)L_i = X_i - R_i\(、右端を \)R_i’ = X_i + R_i\( と置くと、各住民は区間 \)[L_i, R_i’]\( を持っていることになります。 問題は「\)K\( 個の座標 \)P_1, P_2, \dots, P_K\( を選び、少なくとも 1 つの \)P_j$ が含まれる区間の個数を最大化する」ことになります。

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

基地局は実数上のどこにでも設置できますが、候補を有限個に絞り込むことができます。 ある基地局 \(P\) を右（正の方向）へ動かしていくことを考えます。\(P\) を右に動かすと、新しく区間の左端をまたいで受信可能になる住民が増えることはあっても、すでにカバーしている区間の右端を超えるまでは、受信できなくなる住民はいません。 そのため、各基地局はカバーしている区間のいずれかの右端 \(R_i'\) に一致するまで右に寄せても損をしません。

したがって、基地局を置く候補地は \(\{R_1', R_2', \dots, R_N'\}\) の高々 \(N\) 箇所のみを考えれば十分です。

3. 重複カウントをどう防ぐか

基地局を左から順に \(P_1 < P_2 < \dots < P_k\) と設置していくとき、複数の基地局が同一の区間をカバーすることがあります。 単純に各基地局がカバーする区間数を足すと重複して数えてしまうため、各区間を「それを被覆する最も左（最初）の基地局」にのみ計上するというルールを設けます。

区間 \(i\) が基地局 \(P_m\) で初めてカバーされるための必要十分条件は以下の 2 つです： 1. 直前の基地局 \(P_{m-1}\) ではカバーされない：\(P_{m-1} < L_i\) （基地局は昇順に並んでいるため、直前の基地局より左端 \(L_i\) が右にあれば、それ以前のどの基地局でもカバーされません） 2. 基地局 \(P_m\) でカバーされる：\(L_i \le P_m \le R_i'\)

まとめると、 $\(P_{m-1} < L_i \le P_m \le R_i'\)\( となります（ただし \)P0 = -\infty\( とします）。 この条件を満たす区間は直前の基地局 \)P{m-1}\( と現在の基地局 \)P_m$ の 2 点のみに依存して決まります。これにより、直前の状態のみを参照する動的計画法に持ち込むことができます。

---

アルゴリズム

1. 区間の計算と座標の圧縮: 各住民について \(L_i = X_i - R_i, R_i' = X_i + R_i\) を計算します。 候補地となる右端の集合 \(\{R_1', \dots, R_N'\}\) をソートし、重複を削除して \(c_1 < c_2 < \dots < c_M\) （\(M \le N\)）とします。 また、番兵として \(c_0 = -\infty\) を用意します。

2. 遷移コストの前計算: 直前に選んだ基地局が \(c_u\)、次に選ぶ基地局が \(c_v\) (\(0 \le u < v \le M\)) であるときに、新たにカバーされる区間の個数 \(w[u][v]\) を前計算します： $\(w[u][v] = \#\{ i \mid c_u < L_i \le c_v \le R_i' \}\)$

3. 動的計画法 (DP):

   • 状態: \(dp[k][j] :=\) 基地局を \(k\) 個設置し、最後の基地局が \(c_j\) であるときにカバーできる区間数の最大値
   • 初期値: \(dp[1][j] = w[0][j] \quad (1 \le j \le M)\)
   • 遷移: \(k = 2, 3, \dots, \min(K, M)\) について、 $\(dp[k][j] = \max_{1 \le p < j} \{ dp[k-1][p] + w[p][j] \} \quad (1 \le j \le M)\)$

4. 答えの集計: すべての \(k \in [1, \min(K, M)]\) および \(j \in [1, M]\) に対する \(dp[k][j]\) の最大値を出力します。

---

計算量

• 時間計算量:

  • 座標のソートと重複排除: \(O(N \log N)\)
  • 前計算 (\(w[u][v]\)): \(u, v\) の組が \(O(M^2)\) 通りあり、各組について全 \(N\) 個の区間を調べるため \(O(N \cdot M^2) \le O(N^3)\)
  • DPの更新: \(k\) のループが \(O(K)\) 回、\(j\) と \(p\) の 2 重ループが \(O(M^2)\) 回なので \(O(K M^2) \le O(K N^2)\)
  • 全体として \(O(N^3 + K N^2)\) です。\(N \le 250\) より \(N^3 \approx 1.5 \times 10^7\) であり、実行時間制限に十分間に合います。

• 空間計算量:

  • \(w\) のテーブルに \(O(M^2) \le O(N^2)\)、DPテーブルに \(O(K M) \le O(K N)\) を要するため、全体で \(O(N^2 + K N)\) となり、メモリ制限に対しても非常に軽量です。

---

実装のポイント

• \(K > M\) のケース: 基地局を設置できる有効な候補地点の数 \(M\) よりも設置数 \(K\) が大きい場合があります。同じ座標に基地局を重ねて設置しても被覆数は増えないため、基地局数の上限を \(K' = \min(K, M)\) に切り詰めて計算します。

• オーバーフローへの配慮: 座標 \(X_i\) および半径 \(R_i\) は最大 \(10^9\) であるため、\(X_i \pm R_i\) は 32bit 符号付き整数の範囲（約 \(\pm 2 \times 10^9\)）をわずかに超える可能性があります。番兵となる \(-\infty\)（\(-4 \times 10^{18}\) など）も含め、座標の計算には 64bit 整数型（C++の long long）を使用してください。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> L(N), R(N);
    vector<long long> c;
    for (int i = 0; i < N; ++i) {
        long long x, r;
        cin >> x >> r;
        L[i] = x - r;
        R[i] = x + r;
        c.push_back(R[i]);
    }

    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());

    int M = c.size();
    vector<long long> c_pts(M + 1);
    for (int i = 0; i < M; ++i) {
        c_pts[i + 1] = c[i];
    }

    const long long INF = 4e18;
    vector<vector<int>> w(M + 1, vector<int>(M + 1, 0));
    for (int u = 0; u <= M; ++u) {
        long long cu = (u == 0 ? -INF : c_pts[u]);
        for (int v = u + 1; v <= M; ++v) {
            long long cv = c_pts[v];
            int cnt = 0;
            for (int i = 0; i < N; ++i) {
                if (cu < L[i] && L[i] <= cv && cv <= R[i]) {
                    cnt++;
                }
            }
            w[u][v] = cnt;
        }
    }

    int K_prime = min(K, M);
    vector<vector<int>> dp(K_prime + 1, vector<int>(M + 1, 0));

    for (int j = 1; j <= M; ++j) {
        dp[1][j] = w[0][j];
    }

    for (int k = 2; k <= K_prime; ++k) {
        for (int j = 1; j <= M; ++j) {
            int mx = 0;
            for (int p = 1; p < j; ++p) {
                mx = max(mx, dp[k - 1][p] + w[p][j]);
            }
            dp[k][j] = mx;
        }
    }

    int ans = 0;
    for (int k = 1; k <= K_prime; ++k) {
        for (int j = 1; j <= M; ++j) {
            ans = max(ans, dp[k][j]);
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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