概要

電波塔を置ける村（標高 \(P_i \ge K\)）それぞれが「距離 \(D\) 以内を覆う区間」を作るので、全村の位置 \(X_i\)（点）をそれらの区間で全て覆うときの必要区間数の最小値を求める問題です。覆えない点があれば -1 です。

考察

重要な観察：電波塔 1 本＝1 つの区間

標高条件を満たす村 \(i\) に電波塔を置くと、位置 \(X_i\) を中心に半径 \(D\) なので、電波が届く範囲は

• 区間 \([X_i - D,\; X_i + D]\)

になります。
よって問題は次のように言い換えられます：

• 点（全ての村の位置 \(X_i\)）を、選べる区間（標高条件を満たす村が作る区間）で全て覆う
• 使う区間数を最小化

素朴解が難しい理由

• 「どの村に塔を置くか」は最大 \(2 \times 10^5\) 個からの選択で、全探索は不可能です。
• 各点ごとに「覆える区間を全部探す」を愚直にやると \(O(N^2)\) になりやすく、TLE になります。

どう解決するか：左から貪欲

点（村の位置）を左から順に見ていき、「まだ覆われていない最も左の点」を覆うために使える区間の中から

• 右端が最も右まで伸びる区間を選ぶ

のが最適です。これは典型的な「点を覆う最小区間数」問題の貪欲法です。

なぜそれで最小になる？

最も左の未被覆点 \(cur\) を覆うには、左端が \(cur\) 以下の区間をどれか 1 つ必ず選ぶ必要があります。
その中で右端が最も遠いものを選べば、将来覆える点が最大になり、区間数を減らす方向に働きます。
（右端が短い区間を選ぶと、同じ \(cur\) を覆っても先に進めず、後で余計な区間が必要になります。）

アルゴリズム

1. 村を位置 \(X\) でソートし、点列 \(x_0 < x_1 < \dots\) を作る。
2. 標高 \(P_i \ge K\) の村だけから、区間 \([X_i-D,\; X_i+D]\) を作って集め、左端でソートする。
3. 左から順に「未被覆の最左点」 \(cur\) を見ながらスイープする：
   • 左端が \(cur\) 以下の区間を全て候補に追加（優先度付きキュー）。
   • その候補の中から 右端が最大の区間を 1 つ選ぶ（＝塔 1 本設置）。
   • その区間の右端 \(end\) 以下にある点を全て「覆えた」としてスキップする。
   • 候補が空なら、その点は覆えないので -1。
4. 全点を覆えたら、選んだ区間数（塔の本数）を出力する。

実装上の工夫（優先度付きキュー）

• 「右端最大」を高速に取り出したいので、Python の heapq（最小ヒープ）に -end を入れて最大ヒープとして使います。
• 区間を 1 本選んだ後、コードでは heap.clear() しています。
  これは、選んだ区間が「開始位置 \(\le cur\) の区間の中で右端最大」なので、残りの候補は全て右端がそれ以下であり、次の未被覆点（\(end\) より右）を覆うのに役立たないため安全に捨てられる、という理由です。

計算量

• 時間計算量: \(O(N \log N)\)
  （ソート \(O(N \log N)\) ＋ 各区間のヒープ操作合計 \(O(N \log N)\)）
• 空間計算量: \(O(N)\)
  （区間配列とヒープ）

実装のポイント

• 位置 \(X_i\) は入力順ではなく、必ずソートして「左から順に覆う」状態にする。

• 標高条件 \(P_i \ge K\) を満たす村が 1 つもない場合、即 -1。

• スイープ中に「候補区間が存在しない」＝その点を覆えないので -1。

• heapq は最小ヒープなので、最大値を取りたいときは符号を反転して入れる（-end）。

  ソースコード

import sys
import heapq

def main():
    input = sys.stdin.buffer.readline
    N, K, D = map(int, input().split())
    villages = [tuple(map(int, input().split())) for _ in range(N)]
    villages.sort()  # sort by X

    xs = [x for x, _ in villages]

    intervals = []
    for x, p in villages:
        if p >= K:
            intervals.append((x - D, x + D))
    if not intervals:
        print(-1)
        return

    intervals.sort()
    m = len(intervals)

    t = 0  # index over villages (points to cover)
    i = 0  # index over intervals
    heap = []  # max-heap of ends (store -end)
    ans = 0

    while t < N:
        cur = xs[t]

        while i < m and intervals[i][0] <= cur:
            heapq.heappush(heap, -intervals[i][1])
            i += 1

        if not heap:
            print(-1)
            return

        end = -heapq.heappop(heap)
        if end < cur:
            print(-1)
            return

        ans += 1
        heap.clear()

        while t < N and xs[t] <= end:
            t += 1

    print(ans)

if __name__ == "__main__":
    main()

---

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