概要

高速道路を走行する際に、ETCカードを使って連続する \(K\) 個の料金所をスキップすることで、総所要時間を最小化する問題です。

考察

問題の整理

まず、高橋君が目的地に到達するまでの時間を整理しましょう。

• 移動時間: 入口から目的地まで \(G\) メートルを毎秒 \(1\) メートルで移動するので、\(G\) 秒かかります
• 支払い時間: 各料金所 \(i\) で \(T_i\) 秒かかります

ETCカードを使わない場合の総時間は： $\(\text{基本時間} = G + \sum_{i=1}^{N} T_i\)$

重要な気づき

ETCカードを使うと、連続する ちょうど \(K\) 個 の料金所の支払いをスキップできます。

つまり、最短時間を求めるには、支払い時間の合計が最大となる連続 \(K\) 個の料金所を選んでスキップすればよい ということになります。

\[\text{最短時間} = \text{基本時間} - \text{（連続 $K$ 個の支払い時間の最大値）}\]

素朴なアプローチの問題点

連続 \(K\) 個の料金所の支払い時間の和を毎回愚直に計算すると： - 開始位置の候補: \(N - K + 1\) 通り - 各候補に対して \(K\) 個の要素を足す: \(O(K)\) - 合計: \(O(N \times K)\)

\(N\) と \(K\) が最大 \(2 \times 10^5\) の場合、最悪 \(4 \times 10^{10}\) 回の計算となり、TLE になります。

解決策：累積和

累積和（Prefix Sum） を使えば、任意の区間の和を \(O(1)\) で計算できます。

累積和 \(S\) を以下のように定義します： $\(S[0] = 0, \quad S[i] = T_1 + T_2 + \cdots + T_i\)$

すると、区間 \([i, i+K-1]\)（0-indexed で \([i, i+K)\)）の和は： $\(T_i + T_{i+1} + \cdots + T_{i+K-1} = S[i+K] - S[i]\)$

アルゴリズム

1. 入力を読み込む
2. 基本時間 \(G + \sum T_i\) を計算する
3. 支払い時間 \(T\) の累積和を計算する
4. すべての開始位置 \(i = 0, 1, \ldots, N-K\) に対して、連続 \(K\) 個の和 \(S[i+K] - S[i]\) を計算し、最大値を求める
5. 基本時間から最大値を引いて出力する

具体例

\(N=5, K=2, G=100\)、支払い時間が \(T = [3, 7, 2, 8, 1]\) の場合：

• 累積和: \(S = [0, 3, 10, 12, 20, 21]\)
• 連続2個の和:
  • \(i=0\): \(S[2] - S[0] = 10 - 0 = 10\)（\(T_1 + T_2 = 3 + 7\)）
  • \(i=1\): \(S[3] - S[1] = 12 - 3 = 9\)（\(T_2 + T_3 = 7 + 2\)）
  • \(i=2\): \(S[4] - S[2] = 20 - 10 = 10\)（\(T_3 + T_4 = 2 + 8\)）
  • \(i=3\): \(S[5] - S[3] = 21 - 12 = 9\)（\(T_4 + T_5 = 8 + 1\)）
• 最大値: \(10\)
• 最短時間: \(100 + 21 - 10 = 111\) 秒

計算量

• 時間計算量: \(O(N)\)
  • 累積和の計算: \(O(N)\)
  • 最大値の探索: \(O(N - K + 1) = O(N)\)
• 空間計算量: \(O(N)\)
  • 累積和配列に \(O(N)\)

実装のポイント

• 累積和配列は要素数を \(N+1\) にして、\(S[0] = 0\) とすることで、区間の計算が簡潔になります

• \(T_i\) や \(G\) が最大 \(10^9\) であり、総和が大きくなる可能性があるため、64ビット整数が必要ですが、Python では自動的に多倍長整数が使われるので心配不要です

  ソースコード

def solve():
    N, K, G = map(int, input().split())
    
    D = []
    T = []
    for _ in range(N):
        d, t = map(int, input().split())
        D.append(d)
        T.append(t)
    
    # 基本の時間: 移動時間 G秒 + 全ての料金所での支払い時間
    total_T = sum(T)
    base_time = G + total_T
    
    # ETC カードで連続するちょうど K 個の料金所をスキップできる
    # スキップする区間 [i, i+K-1] を選ぶと、T[i] + T[i+1] + ... + T[i+K-1] を節約できる
    # 最大の節約量を求める
    
    # 累積和を使って連続K個の和を高速に計算
    # prefix_sum[i] = T[0] + T[1] + ... + T[i-1]
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + T[i]
    
    # 連続K個の料金所の支払い時間の最大値を求める
    max_saving = 0
    for i in range(N - K + 1):
        # 区間 [i, i+K-1] の和
        saving = prefix_sum[i + K] - prefix_sum[i]
        max_saving = max(max_saving, saving)
    
    # 最短時間 = 基本時間 - 最大節約量
    answer = base_time - max_saving
    print(answer)

solve()

---

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