概要

この問題は、座標上にあるいくつかの候補地点から、隣り合う地点の距離がすべて \(D\) 以下になるように2箇所以上の地点を選び、その建設費用の総和を最小化する問題です。

座標の昇順にソートした上で、動的計画法（DP）とスライド最小値（Monotonic Queue）を組み合わせることで、効率的に最適な選び方を求めることができます。

---

考察

1. 座標によるソートとDPの設計

中継局を左から順に選んでいくことを考えます。まず、候補地点を座標 \(X_i\) の昇順にソートします。

ソート後の \(i\) 番目の地点について、以下の2つの値を管理するDPを考えます。 - \(dp[i]\) : 地点 \(i\) を2番目以降の中継局として選んだときの、そこまでの建設費用の最小合計値。 - \(V[i]\) : 地点 \(i\) を1番目または2番目以降の中継局として選んだときの、そこまでの建設費用の最小合計値。

地点 \(i\) を1番目の候補地点として選ぶ場合の費用は \(C_i\) なので、以下のように表せます。 $\(V[i] = \min(dp[i], C_i)\)$

2. 状態遷移の整理

地点 \(i\) を2番目以降の中継局として選ぶとき、その直前に選んだ中継局を \(j\) （\(j < i\)）とします。 このとき、隣接する中継局間の距離は \(D\) 以下でなければならないため、 \(X_i - X_j \leq D\) を満たす必要があります。

したがって、\(dp[i]\) は以下のように更新できます。 $\(dp[i] = C_i + \min_{j: X_i - X_j \leq D} V[j]\)$

3. 高速化の必要性

もし、各 \(i\) に対して条件を満たす \(j\) を愚直にすべて探索すると、最悪の場合に \(O(N^2)\) の計算量となり、 \(N \leq 2 \times 10^5\) の制約下では実行時間制限（TLE）になってしまいます。

ここで、探索範囲である \(\{j \mid X_i - X_j \leq D\}\) に注目します。\(i\) が進むにつれて、条件を満たす \(j\) の範囲（ウィンドウ）は右側にスライドしていきます。 このように「スライドする区間内の最小値」を効率的に求めるために、スライド最小値（Monotonic Queue）というテクニックを使用します。両端キュー（deque）を用いることで、区間内の最小値を常に \(O(1)\) で取得できるようになります。

---

アルゴリズム

スライド最小値を用いた具体的な手順は以下の通りです。

1. 初期化:

   • 候補地点を座標 \(X_i\) の昇順にソートします。
   • \(dp\) 配列を無限大（inf）で初期化します。
   • 最小値を管理するための両端キュー deq を用意します。deq にはインデックスを格納し、対応する \(V\) の値が昇順（常に先頭が最小値）になるように維持します。

2. 遷移（左から右へループ \(i = 0, 1, \ldots, N-1\)）:

   • ウィンドウの更新（左端の除外）: 現在見ている地点 \(i\) からの距離が \(D\) を超えている地点（\(X_i - X_j > D\) となる \(j\)）を、ウィンドウの左端から除外します。キューの先頭にあるインデックスがこれに該当する場合は、キューから取り除きます。
   • \(dp[i]\) の更新: キューが空でない場合、キューの先頭にあるインデックス \(j = \text{deq}[0]\) が、区間内での \(V[j]\) の最小値を与えます。これを用いて \(dp[i] = C_i + V[j]\) と更新します。キューが空の場合は、直前に置ける中継局が存在しないため \(dp[i] = \infty\) のままです。
   • \(V[i]\) の更新: \(V[i] = \min(dp[i], C_i)\) を計算します。
   • キューの維持（右端の追加）: 新しく得られた \(V[i]\) をキューに追加します。このとき、キューの末尾にある要素の中で \(V[i]\) 以上の値を持つものは、今後最小値として選ばれることはないため、すべてキューから取り除きます（モノトニック性の維持）。その後、 \(i\) をキューの末尾に追加します。

3. 答えの出力:

   • すべての地点における \(dp[i]\) の最小値が答えとなります。最小値が無限大（inf）のままであれば、条件を満たす選び方が存在しないため -1 を出力します。

---

計算量

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

  • 候補地点のソートに \(O(N \log N)\) かかります。
  • DPの遷移において、各インデックス \(i\) はキューに高々1回追加され、高々1回削除されます。したがって、キューの操作にかかる合計時間は \(O(N)\) となり、全体の計算量はソートがボトルネックとなって \(O(N \log N)\) です。

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

  • 候補地点のリスト、DPテーブル、およびキューの保持に \(O(N)\) のメモリを使用します。

---

実装のポイント

• 「2箇所以上」の条件の処理: \(dp[i]\) には「2番目以降として選んだ場合の最小コスト」を格納し、1番目の候補としてのみ選んだ場合のコスト \(C_i\) は \(dp[i]\) には含めないようにしています。これにより、最終的に \(\min(dp)\) を取るだけで、自動的に「2箇所以上選んだ場合」の最小コストを正しく求めることができます。

• スライド最小値の queue の中身: キューには \(V[j]\) の値そのものではなく、インデックス \(j\) を格納します。これにより、座標の距離判定（\(X_i - X_j > D\)）をインデックスから直接行うことができます。

  ソースコード

import sys
from collections import deque


def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    D = int(input_data[1])

    # 座標と建設費用をペアにして格納
    points = []
    idx = 2
    for _ in range(N):
        points.append((int(input_data[idx]), int(input_data[idx + 1])))
        idx += 2

    # 座標の昇順にソート
    points.sort(key=lambda x: x[0])

    dp = [float("inf")] * N
    V = [0] * N

    deq = deque()
    L = 0

    for i in range(N):
        X_i, C_i = points[i]

        # 距離が D より大きい左端の要素をウィンドウから除外
        while L < i and X_i - points[L][0] > D:
            if deq and deq[0] == L:
                deq.popleft()
            L += 1

        # ウィンドウ内に要素が存在する場合、最小値を使って dp[i] を更新
        if deq:
            dp[i] = C_i + V[deq[0]]
        else:
            dp[i] = float("inf")

        V[i] = min(dp[i], C_i)

        # モノトニックキューの維持
        while deq and V[deq[-1]] >= V[i]:
            deq.pop()
        deq.append(i)

    ans = min(dp)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    solve()

---

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