概要

道路上の候補地点から2箇所以上選んで中継局を設置し、隣接する中継局間の距離がすべて \(D\) 以下となるように、建設費用の合計を最小化する問題です。

考察

重要な気づき：最適解は必ず2点のペア

まず、候補地点を座標順にソートして考えます。

核心的な観察: 最適解では、常にちょうど2箇所だけ選べば十分です。

なぜなら、\(k \geq 2\) 箇所を選んだ有効な解があったとき、その中で座標順に隣接するどの2点も距離 \(D\) 以下です。その隣接ペアだけを選んでも有効な解になり、コストは元の解以下です（他の点のコストが正なので）。

つまり、この問題は次のように言い換えられます：

座標の差が \(D\) 以下である2点 \((i, j)\) のペアのうち、\(C_i + C_j\) の最小値を求めよ。

素朴なアプローチ

全ペアを調べると \(O(N^2)\) で、\(N = 2 \times 10^5\) では TLE になります。

効率化

座標順にソートすれば、各点 \(i\) に対して「\(X_i - X_j \leq D\) を満たす \(j < i\)」は連続した区間になります。この区間内の \(C_j\) の最小値を高速に求めればよく、スライディングウィンドウ最小値（単調キュー）で \(O(N)\) に落とせます。

アルゴリズム

1. 候補地点を座標の昇順にソートする。
2. 左端ポインタを管理しながら、各点 \(i\) について以下を行う：
   • 点 \(i-1\) をウィンドウに追加する（単調キューを更新）。
   • ウィンドウの左端から、\(X_i - X_j > D\) となる点を除去する。
   • キューが空でなければ、\(dp_i = C_i + C_{\text{キュー先頭}}\)（= ウィンドウ内の最小コスト）を計算。
3. 全 \(i\) についての \(dp_i\) の最小値が答え。有効なペアがなければ -1。

具体例

\(N=3, D=5\)、点が \((0, 100), (5, 1), (10, 100)\) の場合：

• \(i=1\)（座標5）：ウィンドウに座標0の点。\(5-0=5 \leq 5\) → \(dp = 1 + 100 = 101\)
• \(i=2\)（座標10）：ウィンドウに座標0,5の点。\(10-0=10 > 5\) なので座標0を除去。\(dp = 100 + 1 = 101\)

答え: \(101\)

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的。スライディングウィンドウは \(O(N)\)）
• 空間計算量: \(O(N)\)

実装のポイント

• 単調キュー（deque）: キューにはインデックスを格納し、C[dq[-1]] >= C[i-1] である限り後ろから除去してから追加することで、先頭が常にウィンドウ内の最小コストを持つ点になる。

• ウィンドウの管理: 点 \(i\) に対するウィンドウは「\(i\) より左で、距離が \(D\) 以内」の点。点 \(i\) 自身はウィンドウに入れず、次の点の処理時に追加する点に注意。

• -1 の判定: どの隣接ペアも距離が \(D\) を超える場合は有効な解が存在しないため -1 を出力する。

  ソースコード

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    D = int(input_data[idx]); idx += 1
    
    points = []
    for i in range(N):
        x = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        points.append((x, c))
    
    # Sort by coordinate
    points.sort()
    
    if N < 2:
        print(-1)
        return
    
    # dp[i] = minimum cost of a valid selection where point i is the LAST (rightmost) relay station
    # We need at least 2 stations selected.
    # 
    # For each point i, we can either:
    # 1. Start a new chain: point i is paired with some point j < i where X[i] - X[j] <= D
    #    cost = C[i] + C[j]  -> we want min C[j] for j in valid range
    # 2. Extend an existing chain: dp[i] = C[i] + min(dp[j]) for j where X[i] - X[j] <= D
    #
    # Actually, let's define:
    # dp[i] = minimum total cost of a valid selection (>=2 stations) where station i is the rightmost
    #
    # dp[i] = C[i] + min over j in window { min(dp[j], C[j]) }
    # where window = { j : j < i and X[i] - X[j] <= D }
    #
    # Because if we pick j as the previous station:
    # - If j already has a chain ending at it (dp[j] is valid), cost contribution from left part is dp[j]
    # - If j is the start of a new pair with i, cost contribution is C[j]
    # - So we want min(dp[j], C[j]) over valid j
    #
    # dp[j] >= C[j] always (since dp[j] includes C[j] plus at least one more station's cost)
    # So min(dp[j], C[j]) = C[j] always!
    #
    # Wait, that's not right. dp[j] = cost of chain ending at j with >=2 stations, which includes C[j].
    # So dp[j] >= C[j] + (cost of at least one other station) > C[j].
    # Therefore min(dp[j], C[j]) = C[j].
    #
    # So dp[i] = C[i] + min(C[j]) for j in window where X[i] - X[j] <= D and j < i.
    # And dp[i] is valid (represents a chain of >=2) whenever such j exists.
    #
    # Wait, but this would mean we always just pick pairs? No - because the chain constraint requires
    # ALL consecutive selected stations to be within D. If we select {a, b, c} with a < b < c,
    # we need b-a <= D AND c-b <= D. So it's not just about pairs.
    #
    # The issue: if we select a subset S, ALL consecutive gaps must be <= D.
    # So if we pick the pair (j, i) that's fine - cost C[j] + C[i].
    # If dp[j] represents a valid chain ending at j, and X[i] - X[j] <= D, then we can extend it.
    # Cost = dp[j] + C[i].
    #
    # We want the minimum over all valid chains. The answer is min(dp[i]) for all i.
    #
    # dp[i] = C[i] + min over j in window { min(dp[j], C[j]) }
    # Since dp[j] >= 2*min_cost > C[j] is NOT necessarily true if C[j] is large...
    # Actually dp[j] includes C[j] + at least one more C value, so dp[j] > C[j] if costs are positive.
    # Since C[j] >= 1, dp[j] >= C[j] + 1 > C[j]. So indeed min(dp[j], C[j]) = C[j].
    #
    # Therefore dp[i] = C[i] + min{C[j] : j < i, X[i] - X[j] <= D}
    # Answer = min(dp[i]) over all valid i, or -1.
    
    INF = float('inf')
    
    X = [p[0] for p in points]
    C = [p[1] for p in points]
    
    # Sliding window minimum of C[j] for j in window [left, i-1] where X[i] - X[j] <= D
    ans = INF
    # Use a deque for sliding window minimum of C values
    dq = deque()  # stores indices, C[dq[0]] is the minimum in window
    left = 0
    
    for i in range(N):
        # Add point i-1 to the window (if i > 0)
        if i > 0:
            while dq and C[dq[-1]] >= C[i-1]:
                dq.pop()
            dq.append(i-1)
        
        # Remove points out of window from front
        while dq and X[i] - X[dq[0]] > D:
            dq.popleft()
        
        if dq:
            dp_i = C[i] + C[dq[0]]
            if dp_i < ans:
                ans = dp_i
    
    print(ans if ans < INF else -1)

main()

---

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