概要

予算 \(B\) 以下で連続する遊歩道を整備したとき、通過するスポットのスコア合計（満足度）を最大化する問題です。典型的な「尺取り法（しゃくとり法 / Two Pointers）」で効率的に解けます。

考察

問題の言い換え

区間 \((l, r)\) を選ぶと： - コスト: \(C_l + C_{l+1} + \cdots + C_r\) - 満足度: \(P_l + P_{l+1} + \cdots + P_{r+1}\)

つまり、連続する遊歩道の部分列を選び、コストが \(B\) 以下の範囲で満足度を最大化する問題です。

素朴なアプローチ

すべての \((l, r)\) の組を試すと \(O(N^2)\) 通りあり、各組に対して合計を計算すると最悪 \(O(N^3)\)（累積和を使っても \(O(N^2)\)）です。\(N \leq 5 \times 10^5\) なので、\(O(N^2)\) でも間に合いません。

重要な観察

• コスト \(C_i\) はすべて 正の値 です。
• したがって、\(l\) を固定したとき、\(r\) を大きくするほどコストは単調増加します。
• \(l\) を \(1\) つ右にずらすと、左端の \(C_l\) が取り除かれるのでコストが減り、\(r\) をさらに右に伸ばせる可能性があります。

この単調性のおかげで、尺取り法が使えます。

アルゴリズム

尺取り法（Two Pointers） を使います。

1. 左端 \(l\) を \(0\) から \(N-2\) まで順に動かします（0-indexed）。
2. 各 \(l\) に対して、コストが \(B\) 以下である限り右端 \(r\) をできるだけ右に伸ばします。
3. \(r \geq l\)（少なくとも遊歩道 \(1\) 本を整備）のとき、そのときの満足度で答えを更新します。
4. \(l\) を \(1\) つ右にずらすとき、\(C_l\) をコストから引き、\(P_l\) を満足度から引きます。

具体例 (\(N=5, B=5\)):

スポット:  P = [3, 1, 4, 1, 5]
遊歩道:   C = [2, 3, 1, 4]

\(l\)	\(r\)	コスト	満足度	備考
0	2	\(2+3+1=6 > 5\) → \(r=1\)	\(2+3=5\)	\(P_0+P_1+P_2=3+1+4=8\)
1	2	\(3+1=4 \leq 5\)	\(3+1=4\)	\(P_1+P_2+P_3=1+4+1=6\)
1	2	\(r=3\) は \(4+4=8>5\)	—	\(r\) は \(2\) のまま

\(l\) を右に動かしても \(r\) は戻らないので、全体で \(O(N)\) 回しかポインタが動きません。

計算量

• 時間計算量: \(O(N)\)
  • \(l\) と \(r\) がそれぞれ高々 \(N\) 回しか進まないため、合計 \(O(N)\) です。
• 空間計算量: \(O(N)\)
  • 配列 \(P\), \(C\) の格納に \(O(N)\) が必要です。

実装のポイント

• 初期状態の管理: \(r = l - 1\)（遊歩道をまだ \(1\) 本も選んでいない状態）から始め、sat_sum = P[l]、cost_sum = 0 としておきます。\(r\) を \(1\) つ進めるたびに \(C[r]\) と \(P[r+1]\) を加算します。

• \(r \geq l\) の確認: 遊歩道を少なくとも \(1\) 本整備している場合のみ答えの更新を行います。制約上 \(C_i \leq B\) なので、各 \(l\) に対して \(r = l\) は必ず選べます。

• オーバーフロー対策: \(P_j\) が最大 \(10^9\)、\(N\) が最大 \(5 \times 10^5\) なので、満足度の合計は最大約 \(5 \times 10^{14}\) です。Python では整数のオーバーフローはありませんが、他言語では 64 ビット整数を使う必要があります。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    B = int(input_data[idx]); idx += 1
    
    P = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    C = [int(input_data[idx + i]) for i in range(N - 1)]
    idx += N - 1
    
    # We need to find l, r (1-indexed, 1 <= l <= r <= N-1) such that
    # sum of C[l..r] <= B and sum of P[l..r+1] is maximized.
    # Using 0-indexed: l in [0, N-2], r in [l, N-2]
    # cost = C[l] + ... + C[r]
    # satisfaction = P[l] + P[l+1] + ... + P[r+1]
    
    # Two pointer / sliding window approach
    # We expand r to the right as long as cost <= B, tracking max satisfaction.
    
    # Prefix sums for P and C
    # P_prefix[i] = P[0] + ... + P[i-1]
    # C_prefix[i] = C[0] + ... + C[i-1]
    
    best = -1
    cost_sum = 0
    sat_sum = 0
    
    # l and r are 0-indexed indices into C (0 to N-2)
    # satisfaction for (l, r) = P[l] + P[l+1] + ... + P[r+1]
    # cost for (l, r) = C[l] + C[l+1] + ... + C[r]
    
    l = 0
    # Initialize with l=0, r=0
    # We'll use a sliding window
    
    # sat_sum will track P[l] + ... + P[r+1]
    # cost_sum will track C[l] + ... + C[r]
    
    # Start: l=0, r not yet set. We'll iterate r from 0 to N-2.
    
    sat_sum = P[0]  # P[l] initially, before adding r
    cost_sum = 0
    
    # Actually let me redo this more carefully with two pointers.
    # For each l, find the maximum r such that cost <= B.
    # As l increases, the maximum r can only increase or stay the same.
    
    # We maintain sat_sum = P[l] + ... + P[r+1] and cost_sum = C[l] + ... + C[r]
    # Start with l=0, r=-1 (no road selected yet), sat_sum = P[0], cost_sum = 0
    
    r = -1  # r hasn't been set yet; means no road selected
    sat_sum = P[0]
    cost_sum = 0
    
    for l in range(N - 1):
        # Ensure r >= l
        if r < l:
            r = l - 1
            # Reset: sat_sum should be P[l], cost_sum should be 0
            # But we need to handle this carefully
            # When r = l-1, we haven't selected any road yet for this l
            sat_sum = P[l]
            cost_sum = 0
        
        # Expand r as far as possible
        while r + 1 <= N - 2 and cost_sum + C[r + 1] <= B:
            r += 1
            cost_sum += C[r]
            sat_sum += P[r + 1]
        
        # Now r is the maximum valid r for this l (r >= l - 1)
        # But we need r >= l for a valid selection
        if r >= l:
            if sat_sum > best:
                best = sat_sum
        
        # Move l forward: remove C[l] from cost and P[l] from satisfaction
        if r >= l:
            cost_sum -= C[l]
            sat_sum -= P[l]
        else:
            # r < l means we couldn't even select road l, which contradicts
            # the constraint that C[i] <= B. So this shouldn't happen.
            # But just in case:
            sat_sum = P[l + 1]
            cost_sum = 0
    
    print(best)

main()

---

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