概要

重さの合計が \(K\) 以下となる連続部分区間の中で、満足度の合計が最大となるものを求める問題です。尺取り法（Two Pointers）を用いて効率的に解くことができます。

考察

素朴なアプローチとその問題点

すべての区間 \([l, r]\) を試す方法を考えると、\(l\) と \(r\) の組み合わせは \(O(N^2)\) 通りあります。各区間の重さと満足度を累積和で \(O(1)\) で求めたとしても、\(N\) が最大 \(2 \times 10^5\) のため、\(O(N^2)\) はおよそ \(4 \times 10^{10}\) 回の計算となり、制限時間に間に合いません（TLE）。

重要な気づき

この問題には以下の性質があります：

• 重さ \(B_i\) はすべて 正の値（\(1\) 以上）である
• したがって、区間を右に広げると重さの合計は 単調に増加 する
• 逆に、左端を右にずらすと重さの合計は 単調に減少 する

この 単調性 があるため、右端 \(r\) を固定したとき、重さが \(K\) 以下となる左端 \(l\) の範囲はある値以上の連続した範囲になります。さらに、\(r\) を \(1\) つ増やすと、条件を満たす左端の下限は同じか右に移動します。つまり、左端は後戻りしません。

この性質を利用すると、尺取り法 が適用できます。

具体例

例えば \(N=5\), \(K=10\), \(A = [3, 5, 2, 8, 1]\), \(B = [4, 3, 5, 6, 2]\) の場合：

• \(r=0\): 区間 \([0,0]\)、重さ \(4 \leq 10\) → 満足度 \(3\)
• \(r=1\): 区間 \([0,1]\)、重さ \(7 \leq 10\) → 満足度 \(8\)
• \(r=2\): 区間 \([0,2]\)、重さ \(12 > 10\) → 左端を進めて \([1,2]\)、重さ \(8 \leq 10\) → 満足度 \(7\)
• \(r=3\): 区間 \([1,3]\)、重さ \(14 > 10\) → 左端を進めて \([2,3]\)、重さ \(11 > 10\) → さらに進めて \([3,3]\)、重さ \(6 \leq 10\) → 満足度 \(8\)

このように左端は後戻りせず、全体で \(O(N)\) で処理できます。

アルゴリズム

1. 左端 left を \(0\) に初期化し、重さの合計 sum_b と満足度の合計 sum_a を \(0\) に初期化する
2. 右端 right を \(0\) から \(N-1\) まで順に動かす：
   • sum_a に \(A[\text{right}]\) を加算、sum_b に \(B[\text{right}]\) を加算
   • sum_b > K$ の間、左端の本を区間から除外する（sum_aとsum_bから $A[\text{left}]$, $B[\text{left}]$ を引き、left` を \(1\) 増やす）
   • 現在の sum_a が答えの最大値より大きければ更新する
3. 最終的な最大値を出力する

計算量

• 時間計算量: \(O(N)\) — right は \(N\) 回進み、left も全体で最大 \(N\) 回しか進まないため、合計 \(O(N)\)
• 空間計算量: \(O(N)\) — 配列 \(A\), \(B\) の格納に必要

実装のポイント

• \(K\) が最大 \(10^{15}\)、各 \(B_i\) が最大 \(10^9\)、\(N\) が最大 \(2 \times 10^5\) なので、重さの合計は最大 \(2 \times 10^{14}\) 程度になり得ます。Python では整数のオーバーフローを気にする必要はありませんが、C++ などでは long long を使う必要があります

• while sum_b > K のループで左端を進める際、left が right を超えることはありません（各本の重さが \(K\) 以下の区間が少なくとも1つ存在するため）

• 高速な入力のために 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 = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(N)]; idx += N
    
    ans = 0
    sum_a = 0
    sum_b = 0
    left = 0
    
    for right in range(N):
        sum_a += A[right]
        sum_b += B[right]
        
        while sum_b > K:
            sum_a -= A[left]
            sum_b -= B[left]
            left += 1
        
        if sum_a > ans:
            ans = sum_a
    
    print(ans)

main()

---

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