概要

この問題は、目的地までの移動時間と料金所での待ち時間の合計を最小化する問題です。移動時間は一定であるため、ETCカードを使って「連続する \(K\) 個の料金所の待ち時間の合計」を最大化し、それを全体の待ち時間から差し引くことで最短時間を求めます。

考察

高橋君が目的地に到達するまでにかかる時間は、以下の2つの要素に分けられます。

1. 走行時間: 入口から目的地までの距離 \(G\) を速度 \(1\) で進むため、常に \(G\) 秒かかります。
2. 待ち時間: 各料金所での停止時間 \(T_i\) の合計です。ただし、ETCカードを使うことで連続する \(K\) 個の料金所の待ち時間を \(0\) にできます。

最短時間を求めるためには、「連続する \(K\) 個の料金所の待ち時間の合計」が最大になる区間を見つけ、その分を全体の待ち時間から引けばよいことになります。

素朴なアプローチ

すべての開始位置について、そこから \(K\) 個の料金所の待ち時間を合計する方法（二重ループ）を考えると、計算量は \(O(N \times K)\) となります。今回の制約では \(N, K \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限（通常 2秒程度）に間に合いません。

効率的なアプローチ

「連続する区間の和」を効率よく計算するために、スライディングウィンドウという手法を用います。 隣り合う区間の和（例：\([T_1, \dots, T_K]\) と \([T_2, \dots, T_{K+1}]\)）は、ほとんどの要素が共通しています。そのため、前の区間の和から「抜ける要素 (\(T_1\))」を引いて「新しく入る要素 (\(T_{K+1}\)）」を足すだけで、次の区間の和を \(O(1)\) で求めることができます。

アルゴリズム

1. 全ての料金所の待ち時間の総和 total_waiting_time を計算します。
2. 最初の \(K\) 個の料金所の待ち時間の和を計算し、現在の最大値 max_saved_time とします。
3. 窓（ウィンドウ）を1つずつ右にずらしながら、以下の操作を \(N-K\) 回繰り返します。
   • 現在の和 = 前の和 - (左に外れた待ち時間) + (右に入った待ち時間)
   • max_saved_time を更新する。
4. 最終的な答えを G + total_waiting_time - max_saved_time として出力します。

計算量

• 時間計算量: \(O(N)\)
  • 待ち時間の総和の計算に \(O(N)\)、スライディングウィンドウによる走査に \(O(N)\) かかるため、全体で線形時間となります。
• 空間計算量: \(O(N)\)
  • 各料金所の待ち時間をリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• 入力の高速化: \(N\) が \(2 \times 10^5\) と大きいため、sys.stdin.read().split() などを用いて一括で入力を読み込むと効率的です。

• インデックスの管理: スライディングウィンドウを実装する際、配列の範囲外を参照しないようにループの範囲に注意します。

• 距離 \(D_i\) の扱い: 今回の問題では走行時間は距離 \(G\) のみで決まり、各料金所の位置 \(D_i\) は計算に直接影響しません（すべての料金所が目的地より手前にあるという条件があるため）。したがって、\(T_i\) の値のみに注目すれば解くことができます。

  ソースコード

import sys

def main():
    # 入力を一括で読み込み、スペースや改行で分割してリストにする
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 料金所の数, K: ETCで通過する料金所の数, G: 目的地までの距離
    N = int(input_data[0])
    K = int(input_data[1])
    G = int(input_data[2])
    
    # 各料金所の待ち時間 T_i を抽出する
    # 入力形式は N K G の後に D_i T_i が N 個続くため、T_i はインデックス 4, 6, 8, ... にある
    T = [int(input_data[i]) for i in range(4, 4 + 2 * N, 2)]
    
    # 全ての料金所での待ち時間の合計
    total_waiting_time = sum(T)
    
    # 連続する K 個の料金所の待ち時間の合計の最大値をスライディングウィンドウで求める
    # 最初の K 個の合計を初期値とする
    current_window_sum = sum(T[:K])
    max_saved_time = current_window_sum
    
    # ウィンドウを一つずつずらして最大合計（節約できる時間）を更新する
    for i in range(N - K):
        # 抜ける要素を引いて、新しく入る要素を足す
        current_window_sum = current_window_sum - T[i] + T[i + K]
        if current_window_sum > max_saved_time:
            max_saved_time = current_window_sum
            
    # 最短時間 = (移動距離 G / 速度 1) + (全待ち時間の合計) - (ETCで節約できた待ち時間)
    print(G + total_waiting_time - max_saved_time)

if __name__ == '__main__':
    main()

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