概要

高速道路にある複数の料金所のうち、連続するちょうど \(K\) 個をETCでノンストップ通過することで、所要時間を最小にする問題です。

考察

高橋君は入口から目的地まで毎秒1メートルの速度で移動するので、単純に走る時間は \(G\) 秒です。この間にすべての料金所で停止して支払いをすると、その合計時間が加算されます。つまり、素朴には以下のように考えられます：

• 全料金所で停止する場合の時間 = \(G + \sum_{i=0}^{N-1} T_i\)

しかし、ETCカードにより、連続する \(K\) 個の料金所については停止せずに通過できます。これは、その区間にかかる停止時間を削減できるということです。

したがって、目的は「連続する \(K\) 個の料金所のうち、支払い時間の合計が最大となる区間」を見つけ、その合計を全体の停止時間から引くことで最短時間を求めることになります。

もし素朴にすべての区間について和を計算すると、\(O(NK)\) となり、制約が大きい場合（\(N\) が最大 \(2 \times 10^5\)）には間に合いません。そこで、累積和とスライドウィンドウ（しゃくとり法的な考え方）を用いて、区間和を高速に求めます。

アルゴリズム

1. まず、停止時間の累積和を前処理します。これにより、任意の区間 \([l, r]\) の支払い時間合計を \(O(1)\) で求めることができます。

   • prefix_sum[i] = \(T[0] + T[1] + \cdots + T[i-1]\)
   • 区間 \([l, r]\) の合計 = prefix_sum[r+1] - prefix_sum[l]

2. ETCカードを使う区間として、連続する \(K\) 個の料金所を選ぶことを考えます。そのような区間は全部で \(N - K + 1\) 個あります。

3. 各区間における支払い時間の合計を累積和を使って計算し、最も支払い時間が大きいものを選びます。これを max_etc_saving とします。

4. 最終的な最短時間は： $\( \text{最短時間} = G + \left(\sum_{i=0}^{N-1} T_i\right) - \text{max_etc_saving} \)$

計算量

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

実装のポイント

• 累積和を構築する際、最初に prefix_sum[0] = 0 を入れておくことで、区間和の計算がシンプルになります。
• スライドウィンドウで区間和を計算する際、区間 [i, i+K-1] に対応する和は prefix_sum[i+K] - prefix_sum[i] となります。
• 入力を高速に読み込むため、sys.stdin.read を使用しています。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    G = int(data[idx]); idx += 1
    
    D = [0]*N
    T = [0]*N
    for i in range(N):
        D[i] = int(data[idx]); idx += 1
        T[i] = int(data[idx]); idx += 1

    # 累積和を計算: prefix_sum[i] = T[0] + ... + T[i-1]
    prefix_sum = [0] + list(accumulate(T))
    
    # ETCを使わない場合の合計時間 = 全Tの和
    total_stop_time = prefix_sum[N]
    
    min_etc_saving = 0
    
    # スライドウィンドウで連続K個のTの和を求める
    for i in range(N - K + 1):
        # ETCを使う区間: [i, i+K-1]
        etc_cost = prefix_sum[i + K] - prefix_sum[i]
        saving = etc_cost
        if saving > min_etc_saving:
            min_etc_saving = saving
            
    # 最短時間 = 走る時間 + 停止時間 - ETC節約分
    driving_time = G
    min_time = driving_time + total_stop_time - min_etc_saving
    print(min_time)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。