概要

連続する本の区間で、重さの合計が\(K\)以下となるもののうち、満足度の合計が最大となるものを求める問題です。

考察

素朴なアプローチとしては、すべての連続区間\((l, r)\)について重さの合計と満足度の合計を計算し、条件を満たすものの中から最大の満足度を探す方法が考えられます。しかし、この方法の時間計算量は\(O(N^2)\)となり、\(N\)が最大\(2 \times 10^5\)である本問題では実行時間が非常に長くなってしまいます。

そこで、効率的な解法として「しゃくとり法」が有効です。しゃくとり法は、区間の左端\(l\)と右端\(r\)を適切に動かしながら条件を満たす区間を探索する手法で、各要素が高々2回ずつ処理されるため、線形時間で解くことができます。

アルゴリズム

1. 左端\(l\)を0で初期化し、右端\(r\)を0から\(N-1\)まで順に動かします
2. 各\(r\)について、現在の区間\([l, r]\)の重さ合計を\(current\_weight\)に、満足度合計を\(current\_satisfaction\)に加算します
3. \(current\_weight > K\)となった場合、左端\(l\)を右に動かし、重さ合計が\(K\)以下になるまで\(B[l]\)と\(A[l]\)を減算します
4. 各ステップで条件を満たす区間の満足度合計をチェックし、最大値を更新します

この手法では、\(l\)と\(r\)がそれぞれ\(N\)回しか移動しないため、効率的に探索できます。

計算量

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

実装のポイント

• しゃくとり法の実装では、左端\(l\)が右端\(r\)を超えないように注意します

• 重さの合計が\(K\)を超えた場合の処理をwhileループで正しく行うことが重要です

• 入力値が大きいため、sys.stdin.readを使用して高速に入力処理を行っています

  ソースコード

def main():
    import sys
    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]))
    
    left = 0
    current_weight = 0
    current_satisfaction = 0
    max_satisfaction = 0
    
    for right in range(n):
        current_weight += B[right]
        current_satisfaction += A[right]
        
        while current_weight > K:
            current_weight -= B[left]
            current_satisfaction -= A[left]
            left += 1
            
        if current_satisfaction > max_satisfaction:
            max_satisfaction = current_satisfaction
            
    print(max_satisfaction)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。