概要

座標が \(D\) 以内にある候補地点を 2つ選ぶ とき、建設費用の合計の最小値を求める問題です（存在しなければ -1）。

考察

条件は「選んだ中継局を座標順に並べたとき、隣り合う距離がすべて \(D\) 以下」です。

ここで重要な気づきは次の通りです。

• 建設費用 \(C_i\) はすべて正（\(C_i \ge 1\)）
• よって、中継局を \(3\) 個以上選ぶと必ず費用合計は増える

したがって、条件を満たす選び方が存在するなら、最小費用は必ず \(k=2\)（2箇所だけ設置）で達成できます。
このとき条件は単に

• 2点の距離が \(D\) 以下：\(|X_a - X_b| \le D\)

となるので、問題は

距離が \(D\) 以下のペアのうち、\(C_a + C_b\) の最小値を求めよ

に帰着します。

素朴に全ペアを調べると \(O(N^2)\) で、\(N \le 2\times 10^5\) では間に合いません。
そこで「座標でソート」して、各点について「距離 \(D\) 以内にある過去の点の中で最小コスト」を高速に求めます。

アルゴリズム

1. 候補地点を \((X_i, C_i)\) で受け取り、座標 \(X\) の昇順にソートする。
2. 左端ポインタ \(l\) を使って、各 \(i\) に対して
   • 「\(X_i - X_l \le D\) を満たす最小の \(l\)」を保つ（\(X_i\) から \(D\) 以内にある範囲は \([l, i-1]\)）。
3. 範囲 \([l, i-1]\) に含まれる点の 最小コスト を取り出せれば、最良のペア候補は
   • \(\text{minCostInWindow} + C_i\)
4. 最小コスト管理には ヒープ（優先度付きキュー） を用いる。
   • ヒープには (C[j], j) を入れておく
   • \(l\) より左（範囲外）になった要素は、ヒープ先頭に来たときに捨てる（lazy deletion）

流れ（各 \(i\) で行うこと）： - \(X_i - X_l > D\) の間、\(l\) を右に進める - ヒープ先頭の index が \(l\) 未満なら pop（範囲外なので捨てる） - ヒープが空でなければ ans = min(ans, C[i] + heap_min_cost) - 最後に (C[i], i) をヒープに push

これで「距離 \(D\) 以内の相手の中で最小コスト」を常に高速に得られます。

計算量

• 時間計算量: \(O(N \log N)\)（ソート \(O(N\log N)\) ＋ 各要素の push/pop が高々1回ずつ）
• 空間計算量: \(O(N)\)（ヒープに最大 \(N\) 要素）

実装のポイント

• 座標でソートしないと「距離 \(D\) 以内の過去要素」を連続区間として扱えず、効率化できません。

• ヒープからの削除は直接できないので、heap[0][1] < l の間 pop する lazy deletion が重要です。

• 答えが更新されない（ペアが一つも見つからない）場合は -1 を出力します。

  ソースコード

import sys
import heapq

def main():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    pts = [tuple(map(int, input().split())) for _ in range(N)]  # (X, C)
    pts.sort()
    X = [p[0] for p in pts]
    C = [p[1] for p in pts]

    INF = 10**30
    ans = INF

    heap = []  # (cost, index)
    l = 0

    for i in range(N):
        while l < i and X[i] - X[l] > D:
            l += 1
        while heap and heap[0][1] < l:
            heapq.heappop(heap)

        if heap:
            ans = min(ans, C[i] + heap[0][0])

        heapq.heappush(heap, (C[i], i))

    print(-1 if ans == INF else ans)

if __name__ == "__main__":
    main()

---

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