概要

一本道に並んだ村々に対し、標高条件を満たす場所に最小限の電波塔を設置して、すべての村をカバーする問題です。村が直線上に並んでいるという特性を活かし、端から順番に条件を満たす最適な位置を決定していく「貪欲法（Greedy Algorithm）」を用いて解くことができます。

考察

1. どの村から考えるべきか

すべての村をカバーする必要があるため、まだカバーされていない村のうち「最も左にある村」に注目します。この村をカバーするためには、その村から距離 \(D\) 以内の範囲に少なくとも1つの電波塔を設置しなければなりません。

2. 電波塔をどこに置くのが最適か

ある村（位置 \(x\)）をカバーするために電波塔を設置するとき、その電波塔ができるだけ右側の村も同時にカバーできるように配置するのが、全体の電波塔の数を減らすために最善です。 電波塔の届く範囲は設置場所から前後 \(D\) です。したがって、位置 \(x\) の村をカバーできる範囲 \([x - D, x + D]\) の中で、「標高が \(K\) 以上」かつ「最も右側にある」村に電波塔を設置するのが最も効率的です。

3. なぜこの方法で解けるのか

左端の村をカバーできる候補の中で最も右に電波塔を置くと、その電波塔が右方向に届く限界距離も最大になります。これより左に置くメリット（右側の村をより多くカバーできる可能性）はないため、この選択を繰り返すことで最小数が求められます。

アルゴリズム

1. 事前準備:
   • すべての村を位置 \(X\) の昇順にソートします。
   • 標高 \(P_i \ge K\) を満たす「設置可能な村」の位置リスト eligible_x を抽出します。
2. 貪欲法による選択:
   • 現在まだカバーされていない最も左の村の位置を \(x_{target}\) とします。
   • eligible_x の中から、\(x_{target} + D\) 以下の範囲で最大の位置（最も右）を二分探索で見つけます。これを \(x_{tower}\) とします。
   • 見つかった \(x_{tower}\) が \(x_{target} - D\) 以上であれば、その村に電波塔を設置します。
     • 設置した電波塔は \(x_{tower} + D\) までの村をカバーします。
     • 次に未カバーの村を、位置が \(x_{tower} + D\) より大きい最初の村に更新します。
   • もし適切な \(x_{tower}\) が見つからない場合（範囲内に設置可能な村がない場合）、すべての村をカバーすることは不可能なので -1 を出力して終了します。
3. すべての村がカバーされるまで繰り返し、設置した合計数を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 村のソートに \(O(N \log N)\) かかります。
  • 貪欲法の各ステップで二分探索（bisect_right）を行いますが、各ステップで少なくとも1つの村がカバーされるため、全体でも \(O(N \log N)\) です。
• 空間計算量: \(O(N)\)
  • 村の情報を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 二分探索の活用: 設置可能な村のリストから最適な場所を探す際や、次にカバーすべき村を探す際に bisect_right を使うことで、高速に処理を行うことができます。

• 不可能なケースの判定:

  • 設置可能な村が一つもない場合。
  • 最も左の未カバーの村 \(x_{target}\) に対して、設置可能な村が \(x_{target} - D\) 未満の場所にしかない、あるいは \(x_{target} + D\) を超える場所にしかない場合。 これらのケースでは即座に -1 を返す必要があります。

• 高速な入出力: \(N = 2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

  ソースコード

import sys
from bisect import bisect_right

def solve():
    # 高速な入力読み込みのために sys.stdin.read().split() を使用
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 村の数 N, 設置可能な最小標高 K, 電波の届く距離 D を取得
    N = int(data[0])
    K = int(data[1])
    D = int(data[2])
    
    # 各村の位置 X と標高 P を取得
    villages = [None] * N
    it = iter(data[3:])
    for i in range(N):
        x = int(next(it))
        p = int(next(it))
        villages[i] = (x, p)
    
    # メモリ節約のため、元のデータリストを削除
    del data
    
    # 村を位置 X の昇順にソート
    villages.sort(key=lambda v: v[0])
    
    # 全ての村の位置 X のリスト
    X = [v[0] for v in villages]
    # 電波塔を設置可能な村の位置 X のリスト
    eligible_x = [v[0] for v in villages if v[1] >= K]
    
    # ソート済みの villages リストもメモリ節約のため削除
    del villages
    
    # 設置可能な村が一つもない場合
    if not eligible_x:
        print("-1")
        return

    ans = 0
    i = 0
    while i < N:
        # 現在まだカバーされていない最も左側にある村の位置
        x_target = X[i]
        
        # 強欲法（Greedy Algorithm）:
        # 左端の村 x_target をカバーできる電波塔のうち、
        # 最も右側に設置できる（＝右方向へのカバー範囲が最大になる）村を選択する。
        # その条件は、x_target - D <= tower_x <= x_target + D かつ標高が K 以上。
        
        # 条件 1: tower_x <= x_target + D を満たす最大の tower_x を二分探索で見つける
        idx = bisect_right(eligible_x, x_target + D)
        
        if idx == 0:
            # x_target + D より左側に設置可能な村が一つも存在しない場合
            print("-1")
            return
        
        tower_x = eligible_x[idx - 1]
        
        # 条件 2: 見つけた tower_x が x_target をカバーできるか確認 (tower_x >= x_target - D)
        if tower_x < x_target - D:
            # 設置可能な村の中で最も右にあるものでさえ、x_target まで届かない場合
            print("-1")
            return
        
        # 電波塔を設置
        ans += 1
        
        # この電波塔は [tower_x - D, tower_x + D] の範囲をカバーする。
        # 次にカバーすべき村は、tower_x + D より右側にある最初の村。
        i = bisect_right(X, tower_x + D)
        
    # 必要な電波塔の最小数を出力
    print(ans)

if __name__ == "__main__":
    solve()

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