概要

\(M\) 人の子どもにお菓子 \(S\) 個をルールに従って配った後、指定された区間の子どもたちが持つお菓子の合計を求める問題です。累積和を用いることで各クエリに \(O(1)\) で答えられます。

考察

まず、各子ども \(i\) が最終的に持つお菓子の個数は簡単に計算できます。

• \(q = \lfloor S / M \rfloor\), \(r = S \mod M\) とすると、子ども \(i\) が今回もらう個数は \(i \leq r\) なら \(q + 1\)、\(i > r\) なら \(q\) です。
• よって最終的なお菓子の個数は \(B_i + q + [i \leq r]\)（\([i \leq r]\) は条件が真なら \(1\)、偽なら \(0\)）。

素朴なアプローチの問題点: 各クエリごとに \(L_j\) から \(R_j\) までの合計を愚直に足すと、1つのクエリに最大 \(O(M)\) かかり、全体で \(O(NM)\) となります。\(N, M\) ともに最大 \(2 \times 10^5\) なので、最悪 \(4 \times 10^{10}\) 回の計算が必要になり TLE します。

解決策: 区間の合計を高速に求めたいので、累積和（prefix sum） を使います。あらかじめ各子どもの最終的なお菓子の個数の累積和を計算しておけば、任意の区間 \([L, R]\) の合計を \(O(1)\) で求められます。

アルゴリズム

1. \(q = \lfloor S / M \rfloor\), \(r = S \mod M\) を計算する。
2. 累積和配列 \(\text{prefix}[0..M]\) を構築する：
   • \(\text{prefix}[0] = 0\)
   • \(\text{prefix}[i] = \text{prefix}[i-1] + B_i + q + [i \leq r]\) （\(i = 1, 2, \ldots, M\)）
3. 各クエリ \((L_j, R_j)\) に対して、答えは \(\text{prefix}[R_j] - \text{prefix}[L_j - 1]\) で求まる。

具体例: \(M = 3\), \(S = 7\), \(B = [2, 5, 3]\) の場合

• \(q = 2\), \(r = 1\) なので、配布量は \([3, 2, 2]\)
• 最終的なお菓子: \([2+3, 5+2, 3+2] = [5, 7, 5]\)
• 累積和: \([0, 5, 12, 17]\)
• クエリ \((2, 3)\) → \(\text{prefix}[3] - \text{prefix}[1] = 17 - 5 = 12\)

計算量

• 時間計算量: \(O(M + N)\)
  • 累積和の構築に \(O(M)\)、各クエリの応答に \(O(1)\) × \(N\) 回で \(O(N)\)
• 空間計算量: \(O(M + N)\)
  • 累積和配列に \(O(M)\)、出力バッファに \(O(N)\)

実装のポイント

• 64ビット整数への注意: \(B_i\) が最大 \(10^9\)、\(q\) も最大 \(10^9\) 程度になり得るため、区間合計は \(2 \times 10^{14}\) を超える可能性があります。C++ などでは long long を使う必要がありますが、Python では整数のオーバーフローがないため自動的に対応されます。

• 高速入出力: \(N, M\) が最大 \(2 \times 10^5\) と大きいため、Python では sys.stdin.readline での入力と sys.stdout.write でのまとめて出力を行うことで TLE を回避しています。

• 1-indexed と 0-indexed の変換: 子どもは 1-indexed、配列 \(B\) は 0-indexed なので、B[i-1] でアクセスする点に注意が必要です。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    M, S = map(int, input().split())
    B = list(map(int, input().split()))
    
    q, r = divmod(S, M)
    
    # Build prefix sum of final candy counts
    # Child i (1-indexed): final = B[i-1] + q + (1 if i <= r else 0)
    prefix = [0] * (M + 1)
    for i in range(1, M + 1):
        extra = 1 if i <= r else 0
        prefix[i] = prefix[i - 1] + B[i - 1] + q + extra
    
    N = int(input())
    out = []
    for _ in range(N):
        L, R = map(int, input().split())
        out.append(str(prefix[R] - prefix[L - 1]))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

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