概要

本棚から連続した区間の本を選ぶとき、その区間の重さの合計が \(K\) 以下であり、満足度の合計が最大になるように選ぶ問題。

考察

この問題では「連続する区間」を選ぶ必要があり、区間の重さの合計が \(K\) 以下という制約があります。単純な全探索（すべての \(l, r\) の組み合わせを試す）では、計算量が \(O(N^2)\) となり、\(N\) が最大 \(2 \times 10^5\) なので現実的ではありません。

しかし、区間の重さと満足度の両方が累積和を用いることで高速に求められます。また、「区間の重さが \(K\) 以下」という条件は、右端 \(r\) を固定して左端 \(l\) を適切に動かすことで効率的に判定できます。

ここで重要になるのが「しゃくとり法（two pointers）」です。右端を右に動かしながら、条件を満たす最小の左端を動的に管理することで、無駄な計算を省きます。

例えば、区間 \([l, r]\) が重さの制限を超えた場合、左端 \(l\) を右に動かして制限内に収めるまで繰り返します。このようにして、各区間を二重ループで試すことなく調べることができます。

アルゴリズム

1. 満足度 \(A\) と重さ \(B\) の累積和をそれぞれ前処理で求めておく。
2. 左端 left と右端 right の2つのポインタを使ってしゃくとり法を行う。
3. 各 right に対して、区間 \([left, right]\) の重さが \(K\) 以下になるまで left をインクリメント。
4. 条件を満たす区間の満足度の合計を計算し、最大値を更新していく。

累積和を用いることで、区間の和（満足度 or 重さ）を \(O(1)\) で求めることができるため、全体の計算量を抑えることができます。

計算量

• 時間計算量: \(O(N)\)
  各要素が高々2回（右端と左端で1回ずつ）参照されるため線形時間。
• 空間計算量: \(O(N)\)
  累積和を保存する配列に必要な領域。

実装のポイント

• 累積和を計算する際に、先頭に 0 を追加しておくと、区間和の計算がシンプルになります（例: sum_A[right] - sum_A[left - 1]）。
• left は右端 right に対して単調増加するので、for ループの中で while ループを使って調整します。
• 入力を高速に読み込むために sys.stdin.read を使用しています。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+N]))
    B = list(map(int, data[2+N:2+2*N]))
    
    # 累積和を計算
    sum_A = [0] + list(accumulate(A))
    sum_B = [0] + list(accumulate(B))
    
    max_satisfaction = 0
    left = 1
    
    for right in range(1, N + 1):
        # 区間 [left, right] の重さを計算
        while sum_B[right] - sum_B[left - 1] > K:
            left += 1
        # 満足度の合計を更新
        satisfaction = sum_A[right] - sum_A[left - 1]
        if satisfaction > max_satisfaction:
            max_satisfaction = satisfaction
            
    print(max_satisfaction)

if __name__ == "__main__":
    main()

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