概要

一直線上に並んだ村に対し、標高が \(K\) 以上の村にのみ電波塔を設置でき、各電波塔は距離 \(D\) 以内の村をカバーできるとき、すべての村をカバーするのに必要な電波塔の最小数を求める問題です。

考察

重要な気づき

1. 村を位置順にソートする: 村は一本道に沿って配置されているため、位置順に並べると「左から順にカバーしていく」という考え方ができます。

2. 貪欲法が有効: 左端からまだカバーされていない村を順に処理するとき、その村をカバーできる電波塔候補の中で最も右にある村に設置するのが最適です。なぜなら、右に設置するほど、より多くの右側の村も同時にカバーできる可能性があるからです。

3. カバー条件: 位置 \(x\) にある電波塔は、位置が \([x - D, x + D]\) の範囲にある村をすべてカバーできます。逆に、位置 \(t\) の村をカバーするには、位置が \([t - D, t + D]\) の範囲にある電波塔が必要です。

素朴なアプローチの問題点

各村に対して、すべての電波塔候補を毎回チェックすると \(O(N^2)\) となり、\(N = 2 \times 10^5\) では TLE になります。

解決策

• 電波塔候補のインデックスを保持し、位置順に走査
• 「まだカバーされていない最も左の村」をカバーできる候補を効率的に探索
• 二分探索を活用して、電波塔がカバーする範囲の右端を高速に求める

アルゴリズム

1. 前処理

   • 村を位置 \(X_i\) の昇順にソート
   • 標高 \(P_i \geq K\) を満たす村のインデックスを tower_candidates として抽出
   • 候補が空なら -1 を出力して終了

2. 貪欲法によるカバー

   • covered_until: カバー済みの村の最大インデックス（初期値 -1）
   • tc_idx: 探索開始する電波塔候補のインデックス

以下を繰り返す： - まだカバーされていない最も左の村（インデックス covered_until + 1）を特定 - その村をカバーできる電波塔候補（位置が \([target\_pos - D, target\_pos + D]\) 内）の中で、最も右にあるものを選択 - 該当する候補がなければ -1 を出力 - 選んだ電波塔がカバーする範囲の右端を二分探索で求め、covered_until を更新 - 次の探索のため、tc_idx を適切に進める

1. 終了条件
   • すべての村がカバーされたら、設置した電波塔の数を出力

計算量

• 時間計算量: \(O(N \log N)\)

  • ソート: \(O(N \log N)\)
  • 貪欲法のループ: 各電波塔候補は最大2回程度しか走査されない（尺取り法的な動き）ので \(O(N)\)
  • 二分探索: 各電波塔設置時に \(O(\log N)\)

• 空間計算量: \(O(N)\)

  • 村の情報、位置配列、電波塔候補リストの格納

実装のポイント

1. ソートの重要性: 入力の村は位置順とは限らないため、必ず位置でソートしてから処理を行う。

2. tc_idx の更新: 次にカバーすべき村が決まったら、その村をカバーできない（位置が \(target\_pos - D\) より左の）候補はスキップできる。これにより全体の計算量を抑える。

3. 二分探索の活用: bisect.bisect_right を使い、電波塔がカバーする範囲 \([tower\_pos - D, tower\_pos + D]\) に含まれる村の右端を高速に求める。

4. 不可能判定: 電波塔を設置できる村が存在しない場合や、ある村をカバーできる電波塔候補が見つからない場合は -1 を出力する。

   ソースコード

def solve():
    import sys
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    D = int(input_data[idx]); idx += 1
    
    villages = []
    for i in range(N):
        X = int(input_data[idx]); idx += 1
        P = int(input_data[idx]); idx += 1
        villages.append((X, P))
    
    # 位置でソート
    villages.sort(key=lambda x: x[0])
    
    # 電波塔を設置できる村のインデックス（位置順）
    tower_candidates = []
    for i, (x, p) in enumerate(villages):
        if p >= K:
            tower_candidates.append(i)
    
    if not tower_candidates:
        # 電波塔を設置できる村がない
        print(-1)
        return
    
    # 貪欲法で解く
    # 左から順に、まだカバーされていない最も左の村をカバーする必要がある
    # その村をカバーできる電波塔候補のうち、最も右にある村に電波塔を設置する
    
    n = len(villages)
    count = 0
    covered_until = -1  # covered_until番目の村までカバー済み（-1は何もカバーされていない）
    
    # 各村の位置
    positions = [v[0] for v in villages]
    
    # tower_candidatesは位置順（villagesが位置順にソートされているので）
    tc_idx = 0  # tower_candidatesの現在のインデックス
    
    while covered_until < n - 1:
        # まだカバーされていない最も左の村
        target_village_idx = covered_until + 1
        target_pos = positions[target_village_idx]
        
        # この村をカバーできる電波塔を探す
        # 電波塔の位置xから距離D以内 → |target_pos - x| <= D
        # つまり target_pos - D <= x <= target_pos + D
        
        # 電波塔候補の中で、target_posをカバーでき、かつ最も右にあるものを選ぶ
        # 最も右にあるものを選ぶ理由：より多くの右側の村もカバーできる可能性があるから
        
        best_tower_idx = -1
        best_tower_pos = -1
        
        # tc_idxから探索開始
        # 電波塔候補は位置順なので、target_pos + D を超えたら打ち切り
        for i in range(tc_idx, len(tower_candidates)):
            ti = tower_candidates[i]
            tx = positions[ti]
            
            if tx > target_pos + D:
                # これ以降の候補は全てtarget_posをカバーできない
                break
            
            if tx >= target_pos - D:
                # この電波塔はtarget_posをカバーできる
                if tx > best_tower_pos:
                    best_tower_idx = ti
                    best_tower_pos = tx
        
        if best_tower_idx == -1:
            # target_villageをカバーできる電波塔がない
            print(-1)
            return
        
        # best_tower_idxに電波塔を設置
        count += 1
        
        # この電波塔がカバーできる範囲: best_tower_pos - D <= x <= best_tower_pos + D
        # カバーされる村の最大インデックスを求める
        # 二分探索で best_tower_pos + D 以下の最大位置の村を探す
        
        import bisect
        # positions[i] <= best_tower_pos + D となる最大のi
        max_covered_idx = bisect.bisect_right(positions, best_tower_pos + D) - 1
        
        covered_until = max_covered_idx
        
        # 次回のために、tc_idxを更新（best_tower_pos以降の候補から探索開始）
        # ただし、次のtarget_villageは covered_until + 1 なので、
        # その村をカバーできる電波塔は best_tower_pos より左にある可能性もある
        # なので、tc_idxの更新は慎重に行う
        # 
        # 実際には、次のtargetをカバーするには、target_pos - D 以上の位置の電波塔が必要
        # 次のtarget_pos >= best_tower_pos - D + 1（最悪の場合）なので、
        # 次に必要な電波塔の位置は target_pos - D 以上
        # 
        # 簡単のため、tc_idxはリセットせず、必要に応じて前から探す
        # ただし効率のため、現在のbest_tower_idx以前のものは不要な場合が多い
        
        # tc_idxを、best_tower_pos - D 以上の最初の候補に設定
        # ただし、次のtargetによってはそれより前が必要な場合もある
        # 安全のため、リセットはせず、ただし明らかに不要なものはスキップ
        
        # 次のtargetは covered_until + 1 = max_covered_idx + 1
        # その位置は positions[max_covered_idx + 1]（存在すれば）
        # そのtargetをカバーするには、positions[max_covered_idx + 1] - D 以上の電波塔が必要
        # 
        # tc_idxを更新：positions[tower_candidates[tc_idx]] < next_target_pos - D なら進める
        if covered_until < n - 1:
            next_target_pos = positions[covered_until + 1]
            while tc_idx < len(tower_candidates) and positions[tower_candidates[tc_idx]] < next_target_pos - D:
                tc_idx += 1
    
    print(count)

solve()

この解説は claude4.5opus によって生成されました。