概要

配列の区間和を求め、閾値と比較する問題です。累積和（prefix sum）を用いることで、各クエリに \(O(1)\) で答えることができます。

考察

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

各計画ごとに \(A_{L_i}\) から \(A_{R_i}\) まで愚直に足し合わせると、1回のクエリで最大 \(O(N)\) かかります。計画が \(M\) 個あるので、全体で \(O(NM)\) となり、\(N = 2 \times 10^5\)、\(M = 10^5\) の場合は最大 \(2 \times 10^{10}\) 回の計算が必要になり、制限時間に間に合いません（TLE）。

重要な気づき

区間和の計算は、累積和（prefix sum） を前処理で作っておけば、どんな区間でも \(O(1)\) で求められます。

累積和配列 \(S\) を以下のように定義します：

\[S_0 = 0, \quad S_i = A_1 + A_2 + \cdots + A_i \quad (1 \leq i \leq N)\]

すると、区間 \([L, R]\) の和は次のように計算できます：

\[A_L + A_{L+1} + \cdots + A_R = S_R - S_{L-1}\]

具体例

例えば \(A = [3, -1, 4, 1, 5]\) のとき、累積和は：

\(i\)	0	1	2	3	4	5
\(S_i\)	0	3	2	6	7	12

\(L=2, R=4\) の区間和は \(S_4 - S_1 = 7 - 3 = 4\) で、確かに \(A_2 + A_3 + A_4 = -1 + 4 + 1 = 4\) と一致します。

アルゴリズム

1. 前処理: 配列 \(A\) から累積和配列 \(S\) を \(O(N)\) で構築する。
2. 各クエリへの回答: \(i\) 番目の計画について、区間和 \(s = S_{R_i} - S_{L_i - 1}\) を \(O(1)\) で計算する。
3. 判定: \(s \geq K_i\) なら Dangerous、そうでなければ Safe を出力する。

計算量

• 時間計算量: \(O(N + M)\)（累積和の構築に \(O(N)\)、各クエリの処理に \(O(1)\) × \(M\) 回）
• 空間計算量: \(O(N)\)（累積和配列の分）

実装のポイント

• 1-indexed への対応: 問題文では地点が \(1\) 番目から始まるため、累積和配列を prefix[0] = 0 として長さ \(N+1\) で作り、prefix[R] - prefix[L-1] で区間和を取得します。

• 高速な入出力: Python では sys.stdin.readline を使って入力を高速化し、出力も文字列リストに溜めて最後に '\n'.join(out) で一括出力することで、I/O のオーバーヘッドを抑えています。

• オーバーフローの心配: Python は整数の桁数に制限がないため、\(A_j\) の値が負になる場合や、\(K_i\) が大きな負の値の場合でもオーバーフローを気にせず計算できます。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    # prefix sum
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    out = []
    for _ in range(M):
        L, R, K = map(int, input().split())
        s = prefix[R] - prefix[L - 1]
        if s >= K:
            out.append("Dangerous")
        else:
            out.append("Safe")
    
    print('\n'.join(out))

main()

---

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