概要

車の走行時間は常に \(G\) 秒で一定なので、短縮できるのは「料金所で停止して支払う時間」だけです。ETC を使って 連続するちょうど \(K\) 個の支払いを省略できるとき、合計時間が最小になるように省略区間を選びます。

考察

• 速度は毎秒 \(1\) m で一定なので、入口から目的地（距離 \(G\) m）までの走行時間は必ず \(G\) 秒です。
  料金所の位置 \(D_i\) がどこにあっても、途中で止まる時間を除けば到着時刻は変わりません（止まった分だけ遅れるだけ）。
• よって、到着までの総時間は
  $\( \text{総時間} = G + (\text{支払いに使った総秒数}) \)$ となります。
• ETC を使うと 連続するちょうど \(K\) 個の料金所では支払い時間が \(0\) になります。つまり、
  • 元々の支払い総和を \(S=\sum_{i=1}^{N} T_i\) とすると、
  • ETC 区間に含まれる \(K\) 個の支払い時間の和だけ、総時間を減らせます。
• したがって最短にするには、「連続する長さ \(K\) の区間の \(T\) の和」を最大にする区間を選べばよいです。 $\( \text{答え} = G + \left(S - \max_{\text{連続 }K\text{ 個}} \sum T_i\right) \)$

素朴に「すべての区間（\(N-K+1\) 個）について毎回 \(K\) 個を足す」と \(O(NK)\) になり、最大で \(2\times 10^5\) の制約では間に合いません。

そこで、区間和を高速に更新できる方法（スライディングウィンドウ）を使い、\(O(N)\) で最大区間和を求めます。

アルゴリズム

1. 入力から \(T_1,\dots,T_N\) を読み込み、総和 \(S=\sum T_i\) を計算する（\(D_i\) は今回不要）。
2. 最初の区間 \([1, K]\) の和を window として計算する。
3. 区間を右に1つずつずらしながら、
   • 新しく入る要素を足し、外れる要素を引くことで
     $\( \text{window} \leftarrow \text{window} + T_i - T_{i-K} \)$ と更新する（スライディングウィンドウ）。
   • best に区間和の最大値を保持する。
4. 答えは \(G + (S - \text{best})\)。

（例）\(T=[3,1,4,1,5],\ K=2\) のとき、長さ2の区間和は \(4,5,5,6\) なので最大は \(6\)（最後の \(1+5\)）。
支払い総和は \(14\) なので、支払いにかかる最小時間は \(14-6=8\)、よって総時間は \(G+8\)。

計算量

• 時間計算量: \(O(N)\)（1回の走査で最大区間和を求める）
• 空間計算量: \(O(N)\)（\(T\) を保持。保持しない実装にすれば \(O(1)\) も可能）

実装のポイント

• 走行時間は常に \(G\) 秒なので、\(D_i\) は読んでも使いません（コードでも _ に捨てています）。

• \(T_i\) や総和は最大で \(10^9\)、\(N\) は最大 \(2\times 10^5\) なので、合計は最大 \(2\times 10^{14}\) 程度になります。Python の整数なら安全ですが、他言語では 64-bit 整数を使う必要があります。

• 「ちょうど \(K\) 個」なので、最大区間和は必ず長さ \(K\) のみを対象にします（長さを変えてはいけません）。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    K = next(it)
    G = next(it)

    T = [0] * N
    total = 0
    for i in range(N):
        _ = next(it)          # D_i (unused)
        ti = next(it)
        T[i] = ti
        total += ti

    window = sum(T[:K])
    best = window
    for i in range(K, N):
        window += T[i] - T[i - K]
        if window > best:
            best = window

    ans = G + (total - best)
    print(ans)

if __name__ == "__main__":
    main()

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