概要

連続する区間のお店で商品を購入し、所持金 \(K\) 以内で得られる満足度の合計を最大化する問題。

考察

この問題では、区間 \([l, r]\) を選んで、その区間内のすべてのお店で商品を買う必要があります。このとき、区間の価格の合計が \(K\) 以下でありながら、満足度の合計を最大化する必要があります。

素朴な方法として、すべての区間 \([l, r]\) を全探索する方法があります。しかし、これは \(O(N^2)\) の計算量となり、制約 \(N \leq 2 \times 10^5\) に対しては現実的ではありません（TLEする）。

重要な観察は、「選ぶ区間が連続している」ということです。これにより、尺取り法（two pointers）が有効になります。つまり、右端 \(r\) を伸ばしていき、価格の合計が \(K\) を超えたら左端 \(l\) を縮める、という形で最適な区間を探索できます。

また、各区間の和を高速に求めるために、事前に累積和を計算しておくと便利です。

アルゴリズム

1. 満足度の累積和配列 \(acc_A\) と価格の累積和配列 \(acc_B\) を作成します。これらを使えば任意の区間 \([l, r)\) の和を \(O(1)\) で求められます。
2. 尺取り法（two pointers）を用いて、条件 \(acc_B[r] - acc_B[l] \leq K\) を満たす中で、 $\( acc_A[r] - acc_A[l] \)$ の最大値を求めます。
3. 右端 \(r\) を \(0\) から \(N\) まで動かしながら、左端 \(l\) を適切に進めることで、すべての有効な区間を探索します。

計算量

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

実装のポイント

• 累積和は最初に \(0\) を追加しておくと、区間 \([l, r)\) の和が \(acc[r] - acc[l]\) で統一的に扱えて便利です。

• 尺取り法では、右端を固定して左端を動かすことで、条件を満たす最大の区間を見つけます。

• 条件を満たさない区間は即座に除外するように、whileループで調整します。

  ソースコード

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = [0] * N
    B = [0] * N
    
    idx = 2
    for i in range(N):
        A[i] = int(data[idx])
        B[i] = int(data[idx+1])
        idx += 2

    # 累積和を計算
    acc_A = [0] + list(accumulate(A))
    acc_B = [0] + list(accumulate(B))
    
    max_satisfaction = 0
    left = 0
    
    for right in range(N+1):
        while acc_B[right] - acc_B[left] > K:
            left += 1
        if acc_B[right] - acc_B[left] <= K:
            max_satisfaction = max(max_satisfaction, acc_A[right] - acc_A[left])
    
    print(max_satisfaction)

if __name__ == "__main__":
    main()

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