概要

各住民 \(i\) を区間 \([X_i-R_i,\; X_i+R_i]\) とみなすと、「\(K\) 個の点を置いて、点に刺される（点を含む）区間の個数を最大化せよ」という問題になります。候補位置を区間の左端に限定し、「最後に置いた基地局の位置」を持つ区間 DP で解きます。

考察

1. 区間として言い換える

住民 \(i\) が電波を受信できる条件は \(|X_i - P|\le R_i\)、つまり $\(L_i = X_i - R_i \le P \le X_i + R_i = R'_i\)\( です。よって住民 \)i\( は区間 \)I_i=[L_i, R’_i]\( に対応し、置いた \)K\( 個の点のうち少なくとも 1 つが \)I_i$ に入っていれば良い、という問題になります（最大区間刺し問題）。

2. 候補位置は「区間の左端」だけで十分

実数座標は無限にありますが、最適解では基地局の位置を「どれかの区間の左端」に限って良いことが示せます。

ある基地局 \(P\) が覆う区間の集合を \(S\) とします。\(P\) を少しずつ左に動かしても、\(P \ge \max_{i \in S} L_i\) である限りすべての \(i\in S\) について \(L_i \le P \le R'_i\) が保たれます（右端条件は左に動かすほど緩くなる）。よって \(P\) を \(\max_{i\in S} L_i\) まで移動させても覆う区間は減りません。これは区間の左端です。何も覆わない基地局は答えに影響しないので無視できます。

したがって候補位置は \(L_1,\dots,L_N\) の（重複を除いた）高々 \(N\) 個です。

3. 素朴な方法ではダメな理由

• 全探索: 候補 \(M\ (\le 250)\) 個から \(K\) 個選ぶのは \(\binom{M}{K}\) 通りで到底無理。
• 貪欲法: 「最も多くの区間を覆う点を選ぶ」を繰り返す貪欲は最適になりません。例えば真ん中に大きな塊があってもそこを取ると両側を取り逃す、といった状況が作れます（集合被覆型の貪欲は一般に最適解を与えない）。

4. DP のための重要な観察

候補位置を昇順に \(c_1 < c_2 < \dots < c_M\) とし、基地局を置く候補も左から右の順に選ぶことにします。 \(S(j) = \{i \mid L_i \le c_j \le R'_i\}\)（\(c_j\) を含む区間の集合）とおきます。

ここでのポイントは次の性質です。

補題: \(j_0 < j < j_2\) とする。区間 \(I_i\) が \(c_{j_0}\) と \(c_{j_2}\) の両方を含むなら、\(I_i\) は \(c_j\) も含む。

これは区間が「連続した集合」だからです（\(L_i \le c_{j_0} < c_j < c_{j_2} \le R'_i\)）。

この補題から、新しく \(c_{j_2}\) に基地局を置いたときに新規に覆える区間は、直前に置いた位置 \(c_j\) を含まない区間だけであることが分かります。なぜなら、\(c_{j_2}\) を含み、かつ \(c_j\) より前のどこかの基地局位置に覆われている区間は、必ず \(c_j\) も含む（補題より）ので、\(S(j_2)\setminus S(j)\) に入る区間は「まだ一度も覆われていない」ことが保証されるからです。

つまり、直前の位置だけ覚えれば、重複カウントなしに増分を計算できるという点が本質です。

アルゴリズム

1. 各住民について \(L_i = X_i-R_i,\ R'_i = X_i+R_i\) を計算。
2. 候補位置 \(\{L_i\}\) をソート＆重複削除し \(c_1<\dots<c_M\) とする。
3. 各 \(j\) について、\(c_j\) を含む区間の集合 \(S(j)\) を bitset で持つ。
4. 差分表 \(\mathrm{cnt}[j_2][j] = |S(j_2) \setminus S(j)| = |S(j_2)\ \&\ {\sim}S(j)|\) を前計算（bitset の count()）。
5. DP:
   • \(dp[1][j] = |S(j)|\)
   • \(dp[t+1][j_2] = \max_{j < j_2} \left( dp[t][j] + \mathrm{cnt}[j_2][j] \right)\)
6. 答えは \(\max_{1\le t\le K,\ j} dp[t][j]\)。

\(t < K\) の値も答えの候補にして良いのは、余った基地局を既に置いた場所と同じ座標に重ねて置けるため（同一座標への複数設置が許されている）です。また \(K > M\) のときは \(t=M\) で全候補に置くことになり、すべての区間がその左端で覆われるので答えは \(N\) になります（DP は \(j\) が増加できなくなった時点で打ち切って構いません）。

具体例

\(N=3, K=1\)、区間が \([0,2],[1,5],[4,6]\) の場合、候補は \(0,1,4\)。 - \(S(0)=\{1\},\ S(1)=\{1,2\},\ S(4)=\{2,3\}\)

\(K=1\) なので答えは \(\max(1,2,2)=2\)。\(K=2\) なら例えば \(j=1\)（座標 \(1\)、\(dp=2\)）から \(j=2\)（座標 \(4\)）へ遷移し、\(\mathrm{cnt} = |\{2,3\}\setminus\{1,2\}| = 1\) なので \(3\) となり、全員受信できます。

計算量

\(M \le N\) として

• 時間計算量: 差分表の前計算が \(O(N^3/w)\)（\(w=64\)、bitset による高速化）、DP が \(O(K N^2)\) なので全体で \(O(N^3)\)（\(N=250\) なら約 \(1.5\times10^7\) で十分高速）
• 空間計算量: \(O(N^2)\)（差分表 \(M\times M\) の int 配列、\(250^2\) 程度）

実装のポイント

• \(|X_i| \le 10^9,\ R_i \le 10^9\) なので \(X_i \pm R_i\) は最大 \(2\times10^9\) になり 32bit int をはみ出す。long long で扱うこと。

• 候補位置は必ず重複削除しておく（同じ座標の候補が複数あると DP の「厳密に増加」条件と噛み合わず無駄な計算が増える）。

• \(N \le 250\) なので bitset<256> で足りる。bs[j2] & ~bs[j] の count() で差分数が一発で求まる。

• DP の初期値は「到達不可能」を表す十分小さな負値（\(-10^6\) など）にし、未到達状態から遷移しないようにする。

• 遷移は \(j < j_2\)（左から右へ）に限定する。これは「基地局を座標順に並べて選ぶ」という正規化で、補題の適用に必要。

• 答えは全ての \(t \le K\) にわたって最大値を取る（少ない個数で使い切らなくても良い）。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, K;
    if(scanf("%d %d", &N, &K) != 2) return 0;
    vector<long long> L(N), Rt(N);
    for(int i = 0; i < N; i++){
        long long x, r;
        scanf("%lld %lld", &x, &r);
        L[i] = x - r;
        Rt[i] = x + r;
    }
    // candidate positions: left endpoints
    vector<long long> cand = L;
    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());
    int M = (int)cand.size();

    vector<bitset<256>> bs(M);
    for(int j = 0; j < M; j++){
        long long p = cand[j];
        for(int i = 0; i < N; i++){
            if(L[i] <= p && p <= Rt[i]) bs[j].set(i);
        }
    }

    // cntmat[j][i] = number of intervals containing cand[j] but not cand[i]
    vector<vector<int>> cntmat(M, vector<int>(M, 0));
    for(int j = 0; j < M; j++){
        for(int i = 0; i < M; i++){
            bitset<256> t = bs[j] & (~bs[i]);
            cntmat[j][i] = (int)t.count();
        }
    }

    const int NEG = -1000000;
    // dp[t][j]: max covered with t stations, last at cand[j]
    vector<int> dpPrev(M, NEG), dpCur(M, NEG);
    int ans = 0;
    for(int j = 0; j < M; j++) dpPrev[j] = (int)bs[j].count();
    for(int j = 0; j < M; j++) ans = max(ans, dpPrev[j]);

    for(int t = 1; t < K; t++){
        for(int j = 0; j < M; j++) dpCur[j] = NEG;
        for(int j = 0; j < M; j++){
            if(dpPrev[j] < 0) continue;
            int base = dpPrev[j];
            const vector<int>* row;
            for(int j2 = j + 1; j2 < M; j2++){
                int v = base + cntmat[j2][j];
                if(v > dpCur[j2]) dpCur[j2] = v;
            }
            (void)row;
        }
        bool any = false;
        for(int j = 0; j < M; j++){
            if(dpCur[j] > ans) ans = dpCur[j];
            if(dpCur[j] > NEG) any = true;
        }
        if(!any) break;
        dpPrev = dpCur;
    }

    printf("%d\n", ans);
    return 0;
}

---

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