概要

連続する遊歩道を整備することで散歩コースを作るとき、予算内で得られる満足度の最大値を求めます。

考察

この問題では、区間 \([l, r]\) を選んでその範囲の遊歩道を整備し、対応するスポット \(l\) から \(r+1\) までの満足度を得ます。整備コストの合計が予算 \(B\) 以下である必要があります。

単純な全探索では、\(O(N^2)\) の組み合わせがあり、\(N\) が最大 \(5 \times 10^5\) なので現実的ではありません（TLEになります）。そこで、効率的な方法を考える必要があります。

重要な観察は、コストの累積和と満足度の累積和を使うことで、区間のコストと満足度を高速に求められることです。さらに、コストが予算を超えた場合、左端を右に動かすことで条件を満たす範囲を保ちつつ、満足度の最大値を更新していく「尺取り法」が有効です。

つまり、右端 \(r\) を固定しながら、コストが予算内になるように左端 \(l\) を動かし、その都度満足度を計算して最大値を更新します。

アルゴリズム

1. 各スポットのスコア \(P\) と遊歩道のコスト \(C\) の累積和を前計算します。
2. 尺取り法を用いて、以下を繰り返します：
   • 右端 \(r\) を 1 ずつ増やしながら、区間 \([l, r]\) のコスト \(C_sum[r] - C_sum[l-1]\) を確認。
   • コストが予算 \(B\) を超えていれば、左端 \(l\) を進めます。
   • 条件を満たす区間に対して、対応する満足度 \(P_sum[r+1] - P_sum[l-1]\) を計算し、最大値を更新します。

計算量

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

実装のポイント

• 累積和のインデックス管理に注意（1-based に揃えると分かりやすい）

• 尺取り法では、right を固定して left を適宜動かす

• 最大値の初期値を 0 にしておくこと

  ソースコード

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    B = int(data[1])
    P = list(map(int, data[2:2+N]))
    C = list(map(int, data[2+N:2+N+N-1]))
    
    # 累積和を計算
    P_sum = [0] + list(accumulate(P))
    C_sum = [0] + list(accumulate(C))
    
    max_satisfaction = 0
    left = 1
    for right in range(1, N):
        # コストが予算を超える場合はleftを進める
        while C_sum[right] - C_sum[left-1] > B:
            left += 1
        # 満足度を計算
        satisfaction = P_sum[right+1] - P_sum[left-1]
        if satisfaction > max_satisfaction:
            max_satisfaction = satisfaction
    
    print(max_satisfaction)

if __name__ == "__main__":
    main()

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