概要

\(N\) 冊の本が並んだ本棚から、重さの合計が \(K\) 以下となるような連続する区間を選び、その区間に含まれる本の満足度の合計を最大化する問題です。

考察

1. 素朴なアプローチ（全探索）

まず、すべてのあり得る区間 \([l, r]\) を調べる方法を考えます。区間の選び方は \(O(N^2)\) 通りあり、それぞれの区間について重さと満足度の合計を計算すると、全体で \(O(N^3)\) または累積和を使っても \(O(N^2)\) の計算量がかかります。 今回の制約は \(N \leq 2 \times 10^5\) であるため、\(O(N^2)\) のアルゴリズムでは実行時間制限に間に合いません。

2. 重要な性質：単調性

この問題の重要な点は、「本の重さ \(B_i\) がすべて正である」ことです。 ある区間 \([l, r]\) の重さの合計が \(K\) を超えているとき、その右端をさらに広げた区間 \([l, r+1], [l, r+2], \ldots\) も必ず重さの合計が \(K\) を超えます。 逆に、右端 \(r\) を固定したとき、左端 \(l\) を右に動かせば動かすほど、区間の重さの合計は（あるいは満足度の合計も）減少または維持されます。

このように、区間の端を動かしたときに合計値が単調に変化する性質を利用すると、「しゃくとり法（Two Pointers）」を用いて効率的に解くことができます。

アルゴリズム

しゃくとり法による最適化

「現在の重さの合計が \(K\) 以下である」という条件を保ちながら、区間の左端 left と右端 right を動かしていきます。

1. right を \(0\) から \(N-1\) まで 1 つずつ進めていきます。
2. 新しく区間に加わった本 right の重さを current_weight に、満足度を current_satisfaction に加えます。
3. もし current_weight が \(K\) を超えてしまったら、条件を満たすまで left を右に進め、区間から本を取り除いていきます。
4. current_weight <= K となった時点で、その区間の満足度の合計 current_satisfaction で最大値を更新します。

この方法では、right も left もそれぞれ最大で \(N\) 回しか動きません。そのため、非常に高速に答えを求めることができます。

計算量

• 時間計算量: \(O(N)\)
  • right ポインタが \(N\) 回動き、left ポインタもトータルで最大 \(N\) 回しか動かないため、全体で \(O(N)\) となります。
• 空間計算量: \(O(N)\)
  • 入力された \(A_i\) と \(B_i\) を保持するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N=2 \times 10^5\) と入力サイズが大きいため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 変数の初期化: 最大満足度 max_satisfaction は \(0\) で初期化します。制約により、必ず重さ \(K\) 以下の区間が 1 つは存在するため、最終的な答えは正の整数になります。

• 重さの合計の型: \(K\) や \(B_i\) の累積和は非常に大きな値（最大 \(2 \times 10^{14}\) 程度）になりますが、Pythonは標準で多倍長整数を扱うため、オーバーフローの心配はありません。

  ソースコード

import sys

def solve():
    # 入力を標準入力から取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    
    # 満足度 A と 重さ B のリストを取得
    A = list(map(int, input_data[2:N+2]))
    B = list(map(int, input_data[N+2:2*N+2]))
    
    max_satisfaction = 0
    current_satisfaction = 0
    current_weight = 0
    left = 0
    
    # しゃくとり法 (Two Pointers) を用いて最大値を計算
    for right in range(N):
        current_weight += B[right]
        current_satisfaction += A[right]
        
        # 重さの合計が K を超える間、左端を縮める
        while current_weight > K and left <= right:
            current_weight -= B[left]
            current_satisfaction -= A[left]
            left += 1
        
        # 条件を満たす区間の場合、最大値を更新
        if current_weight <= K:
            if current_satisfaction > max_satisfaction:
                max_satisfaction = current_satisfaction
                
    print(max_satisfaction)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。