概要

\(N\) 軒のお店の商品価格が与えられ、\(Q\) 回のクエリそれぞれについて、指定された区間の合計金額が予算上限 \(T\) を超えるかどうかを判定する問題です。累積和を用いることで各クエリに \(O(1)\) で答えられます。

考察

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

各クエリごとに \(L_j\) 番目から \(R_j\) 番目までの価格を愚直に足し合わせると、1回のクエリあたり最大 \(O(N)\) の計算が必要です。クエリ数 \(Q\) も最大 \(2 \times 10^5\) なので、全体で \(O(NQ)\) となり、最悪 \(4 \times 10^{10}\) 回の計算が必要になります。これでは制限時間に間に合いません（TLE）。

重要な気づき

求めたいものは「配列の連続する区間の合計」です。これは累積和（Prefix Sum）を事前に計算しておくことで、任意の区間の合計を \(O(1)\) で求められるようになります。

アルゴリズム

累積和の構築

累積和配列 \(\text{prefix}\) を次のように定義します：

\[\text{prefix}[0] = 0, \quad \text{prefix}[i] = A_1 + A_2 + \cdots + A_i \quad (1 \leq i \leq N)\]

区間の合計の計算

\(L\) 番目から \(R\) 番目までの合計金額は次の式で \(O(1)\) で求められます：

\[A_L + A_{L+1} + \cdots + A_R = \text{prefix}[R] - \text{prefix}[L-1]\]

具体例

例えば \(A = [3, 1, 4, 1, 5]\) のとき：

\(i\)	0	1	2	3	4	5
\(\text{prefix}[i]\)	0	3	4	8	9	14

\(L=2, R=4\) のとき、合計 \(= \text{prefix}[4] - \text{prefix}[1] = 9 - 3 = 6\) となり、確かに \(A_2 + A_3 + A_4 = 1 + 4 + 1 = 6\) と一致します。

判定

各クエリで求めた合計金額が \(T\) より真に大きいなら Yes、そうでなければ No を出力します。

計算量

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

実装のポイント

• オーバーフローに注意: \(A_i\) は最大 \(10^9\)、\(N\) は最大 \(2 \times 10^5\) なので、区間の合計は最大 \(2 \times 10^{14}\) 程度になります。\(T\) も最大 \(10^{14}\) です。Python では整数のオーバーフローは起きませんが、C++ などで解く場合は long long 型を使う必要があります。

• 高速入出力: \(Q\) が大きいため、Python では sys.stdin.readline による入力高速化と、出力をまとめて sys.stdout.write で行うことで実行時間を短縮しています。

• 1-indexed と 0-indexed の変換: 問題文ではお店の番号が 1 から始まる（1-indexed）ため、累積和配列を prefix[0] = 0 から始めて prefix[R] - prefix[L-1] とすることで、添字のずれを自然に処理しています。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, Q, T = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Build prefix sum array
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    out = []
    for _ in range(Q):
        L, R = map(int, input().split())
        total = prefix[R] - prefix[L - 1]
        if total > T:
            out.append("Yes")
        else:
            out.append("No")
    
    sys.stdout.write("\n".join(out) + "\n")

main()

---

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