概要

連続するお菓子の区間の重さ合計が、袋の最小耐荷重以下となるような区間の個数を求める問題です。

考察

問題の本質は、数列 \(W_1, W_2, ..., W_N\) において、連続する部分列の和が \(C_{\min}\) 以下となるような区間 \((l, r)\) の個数を数えることです。

素朴なアプローチとして、全ての区間 \((l, r)\) について和を計算して条件をチェックする方法が考えられますが、これは \(O(N^2)\) の計算量となり、\(N\) が最大 \(500,000\) という制約では実行時間がかかりすぎてしまいます。

そこで、スライディングウィンドウ法（しゃくとり法）を用いることで効率的に解くことができます。この手法では、右端 \(r\) を順に進めながら、条件を満たすように左端 \(l\) を調整し、各 \(r\) に対して条件を満たす区間の数を効率的に数え上げます。

アルゴリズム

1. 袋の耐荷重の最小値 \(C_{\min}\) を求める
2. 左端ポインタ left を 0 に初期化し、現在の区間和 current_sum を 0 に設定
3. 右端ポインタ right を 0 から N-1 まで順に進める:
   • current_sum に \(W[\text{right}]\) を加算
   • current_sum が \(C_{\min}\) を超えている間、左端を右に移動させながら current_sum から \(W[\text{left}]\) を減算
   • この時点で区間 \([\text{left}, \text{right}]\) は条件を満たすので、右端が right となる有効な区間の数 (right - left + 1) を答えに加算

この手法により、各要素は高々2回（右端として追加される時と左端として除去される時）しか処理されないため、効率的に計算できます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• left ポインタが right を超えないように注意する（left <= right の条件）

• 各区間の和が \(C_{\min}\) を超えた場合、左端を調整して条件を満たすようにする

• 各ステップで有効な区間の数を累積的に加算することで、効率的に総数を計算できる

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    W = list(map(int, data[2:2+n]))
    C_list = list(map(int, data[2+n:2+n+m]))
    
    c_min = min(C_list)
    
    left = 0
    current_sum = 0
    count = 0
    
    for right in range(n):
        current_sum += W[right]
        
        while current_sum > c_min and left <= right:
            current_sum -= W[left]
            left += 1
            
        count += (right - left + 1)
    
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。