概要

一列に並んだ倉庫から荷物を運び、合計重量が制限 \(K\) を超えた（または終点に達した）時点で停止するとき、各スタート地点 \(s\) からの停止位置 \(f(s)\) の区間和を求める問題です。

考察

1. \(f(s)\) の性質

高橋君は倉庫 \(s\) から出発し、倉庫 \(s, s+1, \dots, t\) と進んでいきます。停止する条件は以下の通りです。 - \(A_s + A_{s+1} + \dots + A_t > K\) となる最小の \(t\) - 上記を満たす \(t\) が存在しない場合は \(t = N\)

ここで重要なのは、スタート地点 \(s\) が右に移動すれば、停止位置 \(f(s)\) も右に移動（または同じ位置に留まる）するという「単調性」です。 例えば、倉庫 \(1\) から始めて倉庫 \(5\) で重さを超えたなら、倉庫 \(2\) から始めた場合に倉庫 \(5\) より手前で重さを超えることはありません（荷物の重さ \(A_i\) がすべて正であるため）。

2. 素朴な解法と課題

各クエリ \((L_j, R_j)\) に対して、毎回 \(f(L_j), f(L_j+1), \dots, f(R_j)\) を計算し、さらにそれぞれの \(f(s)\) を求めるために倉庫を走査すると、最悪の場合 \(O(Q \times N^2)\) の時間がかかってしまい、実行時間制限に間に合いません。

この問題を解決するために、以下の2段階の高速化を行います。 1. 尺取り法を用いて、すべての \(s\) に対する \(f(s)\) をまとめて \(O(N)\) で計算する。 2. 累積和を用いて、クエリごとの和を \(O(1)\) で計算する。

アルゴリズム

ステップ1：尺取り法による \(f(s)\) の列挙

「合計重量が \(K\) を超えるまで右端 \(t\) を伸ばす」という操作を、左端 \(s\) を \(1\) から \(N\) まで動かしながら行います。 - \(s\) を \(1\) つ進める際、前回の \(t\) の位置から再開できるため、\(t\) が戻ることはありません。 - 区間の和を高速に計算するために、あらかじめ荷物の重さ \(A_i\) の累積和をとっておきます。

ステップ2：累積和によるクエリ回答

すべての \(s\) について \(f(s)\) が求まったら、次は \(f(s)\) 自体の累積和 \(P\) を作成します。 - \(P[i] = f(1) + f(2) + \dots + f(i)\) これを用意しておくことで、任意の区間 \([L, R]\) における \(f(s)\) の総和は \(P[R] - P[L-1]\) として、たった 1 回の計算で求められます。

計算量

• 時間計算量: \(O(N + Q)\)
  • 荷物の累積和の計算に \(O(N)\)
  • 尺取り法による \(f(s)\) の計算に \(O(N)\) （\(s\) と \(t\) がそれぞれ最大 \(N\) 回しか動かないため）
  • \(f(s)\) の累積和の計算に \(O(N)\)
  • \(Q\) 個のクエリ回答に \(O(Q)\)
• 空間計算量: \(O(N)\)
  • 累積和や配列 \(f(s)\) の格納に \(N\) に比例したメモリを使用します。

実装のポイント

• 尺取り法の条件: 合計重量が \(K\) 以下である限り \(t\) を進めます。ループを抜けたときの \(t\) が「初めて \(K\) を超えた場所」または「終端」になります。

• 高速な入出力: \(N\) や \(Q\) が \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() や sys.stdout.write() を使うことで実行時間を短縮できます。

• インデックスの管理: 累積和を利用する際、配列のサイズを \(N+1\) にして先頭に \(0\) を入れると、範囲和の計算が扱いやすくなります。

  ソースコード

import sys

# Increase recursion depth just in case, though the solution is iterative
sys.setrecursionlimit(200005)

def solve():
    # Read all input at once for faster processing
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: number of warehouses, K: weight limit, Q: number of queries
    N = int(input_data[0])
    K = int(input_data[1])
    Q = int(input_data[2])
    
    # A: weights of the warehouses 1 to N
    A = list(map(int, input_data[3:3+N]))
    
    # S: prefix sums of A to calculate range sums in O(1)
    # S[i] = A_1 + A_2 + ... + A_i
    S = [0] * (N + 1)
    for i in range(N):
        S[i+1] = S[i] + A[i]
        
    # f[s]: the warehouse where Takahashi stops if he starts at warehouse s.
    # Takahashi visits s, s+1, ..., t until:
    # 1. The total weight A[s] + ... + A[t] > K, OR
    # 2. He reaches the last warehouse (t = N)
    f = [0] * (N + 1)
    t = 1
    for s in range(1, N + 1):
        # Ensure t is at least the current warehouse s
        if t < s:
            t = s
        
        # Use a two-pointer approach: as s increases, the stopping point t also increases.
        # We move t forward as long as we haven't reached the end and the cumulative weight is within K.
        while t <= N and S[t] - S[s-1] <= K:
            t += 1
        
        # If the loop ended because t > N, the sum never exceeded K, so he stopped at warehouse N.
        if t > N:
            f[s] = N
        else:
            # If the loop ended because the weight exceeded K, he stopped at warehouse t.
            f[s] = t
            
    # P: prefix sums of f to answer range sum queries for f in O(1).
    # P[i] = f[1] + f[2] + ... + f[i]
    P = [0] * (N + 1)
    for i in range(1, N + 1):
        P[i] = P[i-1] + f[i]
        
    # Process each of the Q queries.
    # Convert query range strings to integers efficiently.
    queries = list(map(int, input_data[3+N:]))
    results = []
    for j in range(Q):
        L = queries[2*j]
        R = queries[2*j+1]
        # The sum f(L) + f(L+1) + ... + f(R) is calculated as P[R] - P[L-1].
        results.append(str(P[R] - P[L-1]))
        
    # Output all query results joined by newlines for efficiency.
    if results:
        sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

---

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