概要

住民 \(i\) が受信できる基地局の設置範囲を区間 \([X_i-R_i,\ X_i+R_i]\) と考えると、「\(K\) 個の点で、できるだけ多くの区間を覆う問題」になります。

設置位置を区間の右端に限定し、基地局を左から順に追加する動的計画法で解きます。

考察

1. 住民を区間に置き換える

\(L_i=X_i-R_i,\ U_i=X_i+R_i\) とします。

住民 \(i\) が受信できる条件は、区間 \([L_i,U_i]\) の中に少なくとも \(1\) 個の基地局があることです。以降、この状態を「区間を覆う」と呼びます。

同じ区間に基地局を複数置いても、その住民は \(1\) 人として数えなければなりません。

2. 設置位置は区間の右端だけ考えればよい

ある基地局が覆っている区間に注目し、その中で最も小さい右端を \(q\) とします。

基地局を現在位置から \(q\) まで右に動かしても、もともと覆っていた区間からは外れません。各区間の左端は現在位置以下であり、右端は \(q\) 以上だからです。

したがって、受信できる住民を減らさずに、各基地局をいずれかの区間の右端へ移動できます。誰も覆っていない基地局は自由に移動して構いません。

そこで、右端を重複除去して昇順に並べた

\(P_0<P_1<\cdots<P_{M-1}\)

だけを設置候補にします。候補数は \(M\le N\) です。

ただし、候補を限定しても、\(K\) 個の選び方をすべて列挙すると組合せ数が大きすぎます。また、各基地局が覆う人数を単純に足すと、複数の基地局から受信できる住民を重複して数えてしまいます。

3. 新しく覆う人数は、直前の基地局だけで決まる

基地局を左から順に設置するとします。現在の最も右の基地局が \(P_p\) にあり、その右の \(P_j\) に新しい基地局を追加する場面を考えます。

\(P_j\) を含む区間 \([L_i,U_i]\) について、次のことが成り立ちます。

• \(L_i\le P_p\) なら、\(L_i\le P_p<P_j\le U_i\) なので、すでに \(P_p\) によって覆われています。
• \(P_p<L_i\) なら、それまでの基地局はすべて \(L_i\) より左にあるので、まだ覆われていません。

よって、新たに覆う区間は、ちょうど

\(P_p<L_i\le P_j\le U_i\)

を満たすものです。

この個数を \(G[p][j]\) とすると、追加で覆う人数を求めるために、それ以前の基地局の配置を覚える必要はありません。最後に置いた基地局の位置だけを状態に持てばよいことが、動的計画法を使える理由です。

例えば、直前の基地局が \(3\)、追加する基地局が \(7\) にある場合、区間 \([2,8]\) はすでに覆われていますが、区間 \([5,9]\) は新たに覆われます。

アルゴリズム

1. 全員を覆える場合を先に処理する

コードでは最初に、全区間を覆うために必要な基地局の最小個数を貪欲法で求めています。

1. 区間を右端の昇順に並べる。
2. まだ覆われていない区間が現れたら、その右端に基地局を置く。

右端が最も左にある未被覆区間は、必ずその区間内のどこかで覆う必要があります。その中で最も右に置けば、後続の区間も覆いやすくなるため、この貪欲法で最小個数を求められます。

必要個数が \(K\) 以下なら、答えは \(N\) です。余った基地局は同じ場所に置けます。

なお、この貪欲法は「全区間を覆うための最小個数」を求めるものです。基地局が足りない場合の「覆う区間数の最大化」は、以降の動的計画法で扱います。

2. 追加で覆う人数を前計算する

各候補 \(P_j\) について、次を求めます。

• \(C[j]\)：\(P_j\) を含む区間の個数
• \(G[p][j]\)：\(P_j\) を含み、かつ \(L_i>P_p\) である区間の個数

すべての組 \((p,j)\) について全区間を調べると \(O(NM^2)\) 時間かかります。コードでは、左端を候補位置に対応付けて集計することで高速化しています。

各区間について、

\(t_i=\min\{t\mid P_t\ge L_i\}\)

を bisect_left で求めます。各区間自身の右端が候補に含まれるため、この添字は必ず存在します。

\(P_j\) を含む区間だけを対象として、buckets[t_i] に個数を集計します。このとき、

\(L_i\le P_p \iff t_i\le p\)

なので、

\(G[p][j]=C[j]-\sum_{t=0}^{p}\mathrm{buckets}[t]\)

となります。

したがって、count = C[j] から始め、\(p=0,1,\ldots,j-1\) の順に buckets[p] を引けば、各 \(G[p][j]\) を求められます。コードでは gains[j][p] に保存しています。

3. 動的計画法を行う

状態を次のように定義します。

\(dp_t[j]\)：異なる候補位置に \(t\) 個の基地局を置き、最も右の基地局を \(P_j\) としたとき、覆える区間数の最大値。

基地局が \(1\) 個の場合は、

\(dp_1[j]=C[j]\)

です。

\(t\ge2\) の場合、直前の基地局の位置 \(P_p\) を全探索して、

\(dp_t[j]=\max_{t-2\le p<j}\left(dp_{t-1}[p]+G[p][j]\right)\)

と遷移します。\(t\) 個の異なる候補を選ぶには、\(j\ge t-1\) である必要があります。

前述の考察より、\(G[p][j]\) は、それまでの配置にかかわらず正確に「新たに覆う人数」を表します。そのため、この遷移で重複なく数えられます。

答えは \(\max_j dp_K[j]\) です。

同じ位置に複数の基地局を置いても受信人数は増えません。また、早期終了しなかった場合は \(K<M\) なので、使用位置が \(K\) 個未満なら未使用の候補を追加できます。追加しても人数は減らないため、異なる \(K\) 個の候補を選ぶ DP で問題ありません。

コードでは、直前の個数の DP 配列だけを保持し、dp と new_dp を使って更新しています。

計算量

候補位置の個数を \(M\) とすると、\(M\le N\) です。

• 時間計算量: \(O(N\log N+NM+M^2+KM^2)\)、最悪で \(O(KN^2)\)
• 空間計算量: \(O(N+M^2)\)、最悪で \(O(N^2)\)

追加人数の前計算に \(O(NM+M^2)\)、動的計画法に \(O(KM^2)\) 時間かかります。空間は主に gains の保存に使用します。

実装のポイント

• 区間は閉区間です。基地局が端点にあっても受信できるため、包含判定は left <= point <= right とします。

• 新たに覆われる条件は left > 前の基地局の位置 です。等しい場合はすでに覆われています。

• 候補位置の重複は除きますが、住民の区間は重複していても除きません。同じ場所・同じ範囲の住民も、それぞれ \(1\) 人として数えます。

• 貪欲法では、left > last のときだけ基地局を追加します。区間を右端順に見ているため、それ以外なら最後に置いた基地局で覆われています。

• DP の更新には別配列を使い、同じ反復内で更新した値を再利用しないようにします。

  ソースコード

import sys
from bisect import bisect_left


def main():
    input = sys.stdin.buffer.readline
    n, k = map(int, input().split())

    intervals = []
    for _ in range(n):
        x, r = map(int, input().split())
        intervals.append((x - r, x + r))

    intervals.sort(key=lambda interval: interval[1])

    needed = 0
    last = -10**30
    for left, right in intervals:
        if left > last:
            needed += 1
            last = right

    if k >= needed:
        print(n)
        return

    points = sorted(set(right for _, right in intervals))
    m = len(points)
    indexed = [
        (left, right, bisect_left(points, left))
        for left, right in intervals
    ]

    gains = []
    dp = [0] * m

    for j, point in enumerate(points):
        buckets = [0] * (j + 1)
        count = 0
        for left, right, threshold in indexed:
            if left <= point <= right:
                buckets[threshold] += 1
                count += 1

        dp[j] = count
        row = [0] * j
        for p in range(j):
            count -= buckets[p]
            row[p] = count
        gains.append(row)

    for used in range(2, k + 1):
        new_dp = [-1] * m
        start = used - 2
        for j in range(used - 1, m):
            row = gains[j]
            best = -1
            for p in range(start, j):
                value = dp[p] + row[p]
                if value > best:
                    best = value
            new_dp[j] = best
        dp = new_dp

    print(max(dp))


if __name__ == "__main__":
    main()

---

この解説は gpt-6-astra-medium によって生成されました。