概要

各グループが指定された範囲のエリアを見学し終わる時刻を求める問題です。累積和を用いることで、任意の区間の見学時間の合計を高速に計算できます。

考察

問題の本質

各グループ \(j\) について、到着時刻 \(S_j\) に見学を開始し、エリア \(L_j\) から \(R_j\) までを順番に見学します。求めるのは「到着時刻 + 見学時間の合計」です。

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

各クエリごとに \(T_{L_j} + T_{L_j+1} + \cdots + T_{R_j}\) を愚直に計算すると、1つのクエリあたり最大 \(O(N)\) の時間がかかります。

\(M\) 個のクエリがあるため、全体で \(O(NM)\) となり、\(N, M\) が最大 \(2 \times 10^5\) の場合、約 \(4 \times 10^{10}\) 回の計算が必要になり、TLE（時間制限超過）になります。

解決策：累積和

区間の合計を高速に求めるには累積和（Prefix Sum）が有効です。

累積和配列 \(\text{prefix\_sum}\) を以下のように定義します： - \(\text{prefix\_sum}[0] = 0\) - \(\text{prefix\_sum}[i] = T_1 + T_2 + \cdots + T_i\)

すると、区間 \([L, R]\) の合計は次の式で \(O(1)\) で求められます： $\(T_L + T_{L+1} + \cdots + T_R = \text{prefix\_sum}[R] - \text{prefix\_sum}[L-1]\)$

具体例

\(T = [3, 1, 4, 1, 5]\) の場合： - \(\text{prefix\_sum} = [0, 3, 4, 8, 9, 14]\)

エリア \(2\) から \(4\) の見学時間の合計は： $\(\text{prefix\_sum}[4] - \text{prefix\_sum}[1] = 9 - 3 = 6 = T_2 + T_3 + T_4 = 1 + 4 + 1\)$

アルゴリズム

1. 前処理：配列 \(T\) の累積和 \(\text{prefix\_sum}\) を計算する
2. 各クエリの処理：
   • 見学時間の合計を \(\text{prefix\_sum}[R] - \text{prefix\_sum}[L-1]\) で計算
   • 終了時刻 \(= S + \text{見学時間の合計}\) を出力

prefix_sum[0] = 0
for i = 1 to N:
    prefix_sum[i] = prefix_sum[i-1] + T[i]

for each query (S, L, R):
    total_time = prefix_sum[R] - prefix_sum[L-1]
    answer = S + total_time

計算量

• 時間計算量: \(O(N + M)\)
  • 累積和の構築に \(O(N)\)
  • 各クエリの処理に \(O(1)\) × \(M\) 個 = \(O(M)\)
• 空間計算量: \(O(N)\)
  • 累積和配列のサイズ

実装のポイント

• 1-indexed と 0-indexed の変換：問題文ではエリア番号が \(1\) から始まるため、累積和の添字に注意が必要です。prefix_sum[L-1] で \(L\) 番目の手前までの和を取得します。

• オーバーフロー対策：\(T_i\) と \(S_j\) がともに最大 \(10^9\)、区間長が最大 \(2 \times 10^5\) なので、答えは最大約 \(2 \times 10^{14}\) 程度になります。Pythonでは整数のオーバーフローを気にする必要はありませんが、他の言語では64ビット整数型を使用する必要があります。

• 高速な入出力：sys.stdin.readline を使用し、結果をまとめて出力することで、入出力のオーバーヘッドを削減しています。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    T = list(map(int, input().split()))
    
    # 累積和を計算
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + T[i]
    
    results = []
    for _ in range(M):
        S, L, R = map(int, input().split())
        # エリアL からエリアR までの見学時間の合計
        total_time = prefix_sum[R] - prefix_sum[L - 1]
        # 終了時刻 = 到着時刻 + 見学時間
        end_time = S + total_time
        results.append(end_time)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

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