概要

所持金 \(K\) 以下で購入できる連続する区間を選び、満足度の合計を最大化する問題です。典型的な尺取り法（Two Pointers）で効率よく解くことができます。

考察

素朴なアプローチ

すべての区間 \((l, r)\) を全探索すると、区間の選び方が \(O(N^2)\) 通りあり、それぞれの区間に対して合計を計算すると最悪 \(O(N^3)\)（累積和を使っても \(O(N^2)\)）かかります。\(N \leq 2 \times 10^5\) なので、\(O(N^2)\) でも間に合いません。

重要な気づき

価格 \(B_i\) はすべて正の値（\(B_i \geq 1\)）です。これは非常に重要な性質で、次のことが言えます：

• 区間を右に広げると、価格の合計は必ず増える
• 区間の左端を右にずらすと、価格の合計は必ず減る

この単調性があるため、尺取り法が適用できます。

具体例で考えてみましょう。\(K = 10\) で以下のお店があるとします：

お店	1	2	3	4
\(A_i\)	5	3	8	2
\(B_i\)	4	3	6	2

右端を \(r = 3\)（お店3）に固定したとき、\(B_1 + B_2 + B_3 = 13 > 10\) なので左端を右にずらし、\(B_2 + B_3 = 9 \leq 10\) で条件を満たします。このとき満足度は \(3 + 8 = 11\) です。

アルゴリズム

尺取り法を用いて、左端 \(l\) と右端 \(r\) の2つのポインタを管理します。

1. 左端 \(l = 0\)、現在の満足度合計 \(\text{sumA} = 0\)、価格合計 \(\text{sumB} = 0\) で初期化する。
2. 右端 \(r\) を \(0\) から \(N-1\) まで順に動かす：
   • \(A[r]\) と \(B[r]\) をそれぞれ \(\text{sumA}\), \(\text{sumB}\) に加える。
   • \(\text{sumB} > K\) である限り、左端のお店を区間から外す（\(A[l]\), \(B[l]\) を引いて \(l\) を1増やす）。
   • ここで \(\text{sumB} \leq K\) なら、区間 \([l, r]\) は条件を満たすので、\(\text{ans} = \max(\text{ans}, \text{sumA})\) と更新する。
3. 最終的な \(\text{ans}\) を出力する。

ポイント: \(l\) が \(r\) を超えた場合（\(l = r + 1\)）、それは「お店 \(r\) 単体でも価格が \(K\) を超える」ことを意味します。このとき \(\text{sumB} = 0 > K\) とはならないので、\(\text{sumB} \leq K\) の条件チェックで自然に弾かれ、答えは \(0\) のまま更新されません。

なぜ正しいか: 右端 \(r\) を固定したとき、価格合計が \(K\) 以下となる最小の左端 \(l\) を見つければ、それが満足度合計を最大にする区間です（\(A_i\) がすべて正なので、区間は広いほど満足度が大きい）。尺取り法により、\(l\) は全体を通して単調に増加するため、すべての \(r\) について効率よく最適な \(l\) が求まります。

計算量

• 時間計算量: \(O(N)\) — 左端 \(l\) と右端 \(r\) はそれぞれ最大 \(N\) 回しか進まないため
• 空間計算量: \(O(N)\) — 配列 \(A\), \(B\) の格納

実装のポイント

• \(K\) が最大 \(10^{14}\) と大きいので、C++ などでは long long を使う必要があります。Python では整数のオーバーフローは起きないため特に注意は不要です。

• 条件を満たす区間が存在しない場合、答えは \(0\) です。初期値を \(0\) にしておけば自然に処理されます。

• 入力が大きくなり得るため、sys.stdin.buffer.read() でまとめて読み込むと高速化できます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i] = int(input_data[idx]); idx += 1
        B[i] = int(input_data[idx]); idx += 1
    
    ans = 0
    current_sum_a = 0
    current_sum_b = 0
    left = 0
    
    for right in range(N):
        current_sum_a += A[right]
        current_sum_b += B[right]
        
        while current_sum_b > K and left <= right:
            current_sum_a -= A[left]
            current_sum_b -= B[left]
            left += 1
        
        if current_sum_b <= K and left <= right + 1:
            if left <= right:
                ans = max(ans, current_sum_a)
            elif left == right + 1:
                # All elements were removed, no valid interval ending at right
                pass
            else:
                ans = max(ans, current_sum_a)
    
    # Simpler logic: if left <= right after the while loop, we have a valid interval
    # Let me redo this cleanly
    
    ans = 0
    current_sum_a = 0
    current_sum_b = 0
    left = 0
    
    for right in range(N):
        current_sum_a += A[right]
        current_sum_b += B[right]
        
        while current_sum_b > K and left <= right:
            current_sum_a -= A[left]
            current_sum_b -= B[left]
            left += 1
        
        if current_sum_b <= K:
            ans = max(ans, current_sum_a)
    
    print(ans)

main()

---

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