概要

村の位置と標高が与えられ、指定された条件の下で全ての村をカバーするための電波塔の最小設置数を求める問題。

考察

この問題では、各村が電波塔からの電波を受信できるかどうかを判定し、さらにその条件を満たす最小の電波塔数を求めなければなりません。

まず重要なのは、村は位置順に並べて考えると処理しやすいということです。また、電波塔は「標高 \(K\) 以上」の村にしか設置できないので、設置可能な候補の村だけを別に管理しておくと効率的です。

次に、すべての村が少なくとも1つの電波塔によってカバー可能であることを確認する必要があります。つまり、各村について、前後 \(D\) メートル以内に標高 \(K\) 以上の村が存在するかをチェックします。もし存在しなければ、条件を満たせないので -1 を出力します。

最後に、実際に電波塔を設置する際に、貪欲法を用います。これは、「今見ている村をカバーするために、最も遠くまでカバーできる電波塔を設置する」という戦略です。つまり、今注目している村をカバーできる範囲の中で、最も右側にあり、かつ標高 \(K\) 以上の村に電波塔を設置することで、以降の多くの村も同時にカバーできます。

この貪欲法の正当性は、「より右に設置すれば、それだけ多くの村をカバーできる」ことから来ています。また、二分探索を用いることで、高速に範囲内の候補を見つけることができます。

アルゴリズム

1. 入力を読み込み、村を位置順にソートする
2. 標高 \(K\) 以上の村のインデックスを cand_indices として保持
3. 各村に対し、距離 \(D\) 以内に標高 \(K\) 以上の村が存在するかを二分探索でチェック
   • 存在しなければ -1 を出力して終了
4. 貪欲法により電波塔の最小数を求める
   • 左端の村から順に、カバーできる範囲内で最も右の標高 \(K\) 以上の村に電波塔を設置
   • 設置した電波塔でカバーできる村をスキップ
5. 設置した電波塔数を出力

計算量

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

時間計算量は、主にソートと二分探索による部分が支配的です。各村に対して二分探索を用いて候補を探す操作が \(O(\log N)\) であり、それが \(N\) 回繰り返されるため、全体で \(O(N \log N)\) となります。

実装のポイント

• 村を位置順にソートする際、標高の情報も一緒に管理する必要がある
• 電波塔設置可能村（標高 \(K\) 以上）のインデックスリスト cand_indices を持つことで、二分探索が容易になる
• 貪欲法で「最も右の設置可能な村」を探す際にも、位置配列に対する二分探索と、そこから左に戻って最初の候補を探すロジックが必要
• 範囲外アクセスに注意し、境界条件の扱いは慎重に行う

## ソースコード

```python
import sys
from bisect import bisect_left, bisect_right

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    D = int(data[idx])
    idx += 1
    
    X = []
    P = []
    for _ in range(N):
        x = int(data[idx])
        idx += 1
        p = int(data[idx])
        idx += 1
        X.append(x)
        P.append(p)
    
    # 村を位置順にソート
    villages = sorted(zip(X, P))
    X_sorted = [v[0] for v in villages]
    P_sorted = [v[1] for v in villages]
    
    # 電波塔を設置可能な村のインデックスをリストアップ
    cand_indices = []
    for i in range(N):
        if P_sorted[i] >= K:
            cand_indices.append(i)
    
    # 各村が被覆可能かチェック
    for i in range(N):
        # 二分探索で距離D以内に標高K以上の村があるか確認
        x = X_sorted[i]
        left = bisect_left(X_sorted, x - D)
        right = bisect_right(X_sorted, x + D) - 1
        # [left, right] の範囲内に標高K以上の村があるか
        # cand_indices は昇順なので、これも二分探索可能
        l_idx = bisect_left(cand_indices, left)
        r_idx = bisect_right(cand_indices, right)
        if l_idx >= r_idx:
            print(-1)
            return
    
    # 被覆可能な場合、貪欲法で最小タワー数を求める
    # 左端から見て、カバーできる最も右の候補地にタワーを設置
    count = 0
    i = 0
    while i < N:
        # 村iをカバーするには、[X_sorted[i] - D, X_sorted[i] + D] 内にタワーが必要
        # タワーはこの範囲内で最も右（X_sortedが大きい）かつ標高K以上である村に設置するのが最適
        # 最も右の候補を探す
        right_limit = X_sorted[i] + D
        # X_sortedの中でright_limit以下の最大の要素のインデックスを求める
        pos = bisect_right(X_sorted, right_limit) - 1
        
        # このposから左方向にさかのぼって、最初に見つかる標高K以上の村が最適な設置場所
        tower_pos = -1
        j = pos
        while j >= 0:
            if P_sorted[j] >= K:
                tower_pos = j
                break
            j -= 1
        
        if tower_pos == -1:
            print(-1)
            return
        
        # このタワーでカバーできる最も右の村を見つける
        coverage_end = X_sorted[tower_pos] + D
        while i < N and X_sorted[i] <= coverage_end:
            i += 1
        
        count += 1
    
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。