概要

数列 \(W\) から連続する部分列を選ぶとき、その和が \(C\) の最小値以下となるような選び方は何通りあるかを求める問題です。

考察

この問題では、お菓子の重さの列 \(W_1, W_2, \ldots, W_N\) の中から「連続する区間」\([l, r]\) を選び、その区間の和が袋の耐荷重の最小値 \(C_{\min}\) 以下であるものをカウントする必要があります。

単純には、すべての区間 \([l, r]\) を全探索して和を計算すれば正しい答えは得られますが、これは \(O(N^2)\) の計算が必要になり、制約 \(N \leq 5 \times 10^5\) では明らかに時間内に終わりません。

そこで、「区間の和」を高速に求められる 累積和 を使います。さらに、条件を満たす区間の数を効率よく数えるために、尺取り法（Two Pointers）というテクニックを利用します。

尺取り法では、右端 \(r\) を固定したときに、左端 \(l\) がどこまで左に伸びていいかを動的に管理しながら、条件を満たす区間の数を数えていきます。これにより、各 \(r\) に対して \(O(1)\) で対応する \(l\) の範囲を求めることができ、全体で \(O(N)\) 時間で解けます。

アルゴリズム

1. まず、袋の耐荷重の最小値 \(C_{\min} = \min(C_1, C_2, \ldots, C_M)\) を求めます。
2. 次に、お菓子の重さの列 \(W\) の 累積和 \(S\) を計算します：
   • \(S[i] = W_1 + W_2 + \cdots + W_i\)
   • \(S[0] = 0\) としておくと、区間 \([l, r]\) の和は \(S[r] - S[l-1]\) で求められます。
3. 尺取り法により、各右端 \(r\) に対して条件を満たす最大の左端 \(l\) を求めます：
   • \(S[r] - S[l] \leq C_{\min}\) を満たす最大の \(l\) を見つけます。
   • このとき、区間 \([l+1, r], [l+2, r], \ldots, [r, r]\) のすべてが条件を満たすので、\(r - l\) を答えに加算します。

計算量

• 時間計算量: \(O(N + M)\)
  • 最小値の計算が \(O(M)\)、尺取り法が \(O(N)\)。
• 空間計算量: \(O(N + M)\)
  • 入力を格納する配列と累積和の配列が必要。

実装のポイント

• 累積和を計算する際に、先頭に \(0\) を追加しておくと区間和の計算が簡単になります。

• 尺取り法では、右端を1つずつ進めながら、条件を満たさなくなるまで左端を進めることで効率よく数え上げます。

• 区間 \([l, r]\) の和が \(S[r] - S[l-1]\) となることに注意し、コード中のインデックス管理を慎重に行いましょう。

  ソースコード

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    W = list(map(int, data[2:2+N]))
    C = list(map(int, data[2+N:2+N+M]))
    
    # 袋の最小耐荷重を求める
    C_min = min(C)
    
    # 累積和を計算
    S = [0] + list(accumulate(W))
    
    # 尺取り法 (two pointers) で条件を満たす区間の数を数える
    count = 0
    left = 0
    
    for right in range(1, N+1):
        # 区間 [left+1, right] の和が C_min 以下になるまで left を進める
        while S[right] - S[left] > C_min:
            left += 1
        # この時点で [left+1, right], [left+2, right], ..., [right, right] がすべて条件を満たす
        count += right - left
    
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。