概要

住民 \(i\) は「区間 \([X_i-R_i,\;X_i+R_i]\) の中に基地局があれば電波を受信できる」と言い換えられます。つまり \(N\) 個の区間が与えられ、\(K\) 個の点を打って「少なくとも 1 個の点を含む区間」の数を最大化する 問題です（区間刺し・最大被覆問題）。

考察

1. 区間の問題に言い換える

\(L_i = X_i - R_i,\; R'_i = X_i + R_i\) とおくと、住民 \(i\) が電波を受信できる \(\iff\) 選んだ点のどれかが \([L_i, R'_i]\) に入る、です。以降この区間を単に \([L_i,R_i]\) と書きます。

2. 座標は実数だが、候補は \(N\) 通りだけ

「好きな実数座標」と言われても、候補が無限にあるままでは扱えません。しかし次が言えます。

最適解のうち、すべての点が「どれかの区間の右端 \(R_i\)」に置かれているものが存在する。

理由：ある点 \(p\) が担当している（=その点のおかげで被覆されている）区間の集合を \(S\) とすると、\(p\) を右へ動かしても \(\min_{i\in S} R_i\) までは \(S\) のすべての区間に入り続けます。そこまで動かせば \(p\) はある区間の右端に一致します。これを各点について行えばよいです。

よって候補座標は \(R_1,\dots,R_N\) の（重複を除いた）\(m\ (\le N)\) 個だけを考えれば十分です。

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

候補 \(m\) 個から \(K\) 個選ぶ全探索は \(\binom{m}{K}\) 通りで到底間に合いません。また「一番多くの区間を刺す点を貪欲に選ぶ」という方法は最大被覆問題なので貪欲では最適になりません（例：区間 \(A,B\) を刺す点と、\(A\) だけ・\(B\) だけを刺す点があるとき、\(K=2\) では後者 2 つを選ぶ方が良い場合がある）。

そこで DP を使います。ここでポイントになるのが「二重に数えないための工夫」です。

4. 二重カウントを避ける鍵となる補題

候補座標を \(c_1 < c_2 < \dots < c_m\) とし、点を左から順に置いていくことにします。直前に置いた点が \(c_i\)、今置く点が \(c_j\)（\(i<j\)）だとします。このとき

区間 \([L,R]\) が \(c_j\) を含み、かつ \(L \le c_i\) ならば、その区間は \(c_i\) も含む。

（証明：\(c_i < c_j \le R\) かつ \(L \le c_i\) なので \(c_i \in [L,R]\)。）

したがって「\(c_j\) を含む区間のうち、まだ数えられていないもの」は $\(\text{cnt}[j][i] = \#\{\,k : L_k \le c_j \le R_k \ \text{かつ}\ L_k > c_i \,\}\)\( にちょうど一致します（\)L_k > c_i\( なら \)c_i$ 以下のすべての既存の点より左端が右にあるので、まだ一度も数えられていない）。これで各区間は「それが含む最も左の選んだ点」でちょうど 1 回だけ数えられます。

アルゴリズム

1. 各住民から区間 \([L_i,R_i]=[X_i-R_i,\,X_i+R_i]\) を作る。
2. 候補座標 \(c_1<\dots<c_m\) を右端 \(R_i\) の重複除去・ソートで作る。便宜上 \(c_0=-\infty\)（「まだ点を置いていない」を表す）とする。
3. \(\text{cnt}[j][i]\)（\(1\le j\le m\), \(0\le i<j\)）を前計算する。 固定した \(j\) について、\(c_j\) を含む各区間 \([L,R]\) は「\(c_i < L\) を満たす \(i\)」すべてに \(+1\) 寄与するので、\(L\) の位置を二分探索して差分配列 + 累積和で \(i\) について一括計算できる。
4. DP：
   • \(dp_t[j] =\) 「点を \(t\) 個使い、\(t\) 個目を \(c_j\) に置いたときの被覆区間数の最大値」
   • 遷移：\(dp_t[j] = \max_{0\le i<j}\bigl(dp_{t-1}[i] + \text{cnt}[j][i]\bigr)\)（\(dp_0[0]=0\)）
   • 答えは \(t=1,\dots,\min(K,m)\) の全 \(dp_t[j]\) の最大値。
5. \(K\) 個ぴったり置く必要があるが、同じ座標に複数置いてよいので、実質的に使う点が \(t\ (\le K)\) 個でも問題ない。よって \(t\) を \(\min(K,m)\) まで回して最大値をとればよい。

計算量

\(m \le N\) として

• 時間計算量: \(O(N^2\log N + K N^2)\)（前計算 \(O(m(n\log m + m))\)、DP \(O(K m^2)\)）。\(N\le 250\) なので \(250^3 \approx 1.6\times 10^7\) 程度。
• 空間計算量: \(O(N^2)\)（\(\text{cnt}\) テーブル）

実装のポイント

• \(\text{cnt}[j][i]\) を毎回 \(O(N)\) で数えると \(O(K N^3)\) になり間に合いません。 固定した \(j\) について、\(c_j\) を含む区間の左端 \(L\) に対し bl = bisect_left(cands, L)（= \(c_i < L\) となる \(c_i\) の個数）を求め、diff[0] += 1; diff[bl+1] -= 1 として累積和を取れば、\(i=0..m\) 全部の値が一度に求まります。\(i=0\) は \(c_0=-\infty\) に対応し、\(\text{cnt}[j][0]\) は「\(c_j\) を含む区間の総数」になります。

• DP の初期値には十分小さい負値（NEG）を入れ、「到達不可能」と区別します。\(t\) 個目を \(c_j\) に置くには \(j\ge t\) が必要なので、そこは自然に NEG のままになります。

• \(t\) が \(m\) を超えても意味がないので min(K, m) まででループを打ち切ります。また答えが \(N\) に達したら即 break すると高速です。

• 座標は \(|X|\le 10^9,\ R\le 10^9\) なので \(L,R\) は \(2\times10^9\) 程度になります（C++ 等では 64bit 整数、または int でもぎりぎり収まるが long long 推奨）。

• 「区間の右端」だけを候補にすれば十分という点に注意（左端も混ぜても正しいが、補題 \(L\le c_i \Rightarrow c_i\) を含む、の議論と DP の整合性は右端候補で綺麗に閉じます）。

  ソースコード

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    Ls = [0]*n; Rs = [0]*n
    for i in range(n):
        x = int(data[2+2*i]); r = int(data[3+2*i])
        Ls[i] = x - r
        Rs[i] = x + r
    cands = sorted(set(Rs))
    m = len(cands)
    NEG = -(1 << 30)

    # cnt[j][i] = number of intervals with L > c_i and L <= c_j <= R
    cnt = [None]*(m+1)
    for j in range(1, m+1):
        p = cands[j-1]
        diff = [0]*(m+2)
        for i in range(n):
            li = Ls[i]
            if li <= p and p <= Rs[i]:
                bl = bisect_left(cands, li)
                diff[0] += 1
                diff[bl+1] -= 1
        s = 0
        arr = [0]*(m+1)
        for i in range(m+1):
            s += diff[i]
            arr[i] = s
        cnt[j] = arr

    dp = [NEG]*(m+1)
    dp[0] = 0
    ans = 0
    tmax = K if K < m else m
    for t in range(1, tmax+1):
        nd = [NEG]*(m+1)
        for j in range(1, m+1):
            cj = cnt[j]
            best = NEG
            for i in range(j):
                v = dp[i]
                if v > NEG:
                    w = v + cj[i]
                    if w > best:
                        best = w
            nd[j] = best
        cur = max(nd)
        if cur > ans:
            ans = cur
        if ans >= n:
            break
        dp = nd
    print(ans)

main()

---

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