概要

予算 \(B\) 以内で整備できる「連続する遊歩道区間」を選び、その区間で訪れられるスポットのスコア合計（満足度）を最大化します。

考察

整備区間を \((l,r)\)（\(1 \le l \le r \le N-1\)）とすると、

• コスト：\(C_l + C_{l+1} + \cdots + C_r\)
• 満足度：\(P_l + P_{l+1} + \cdots + P_{r+1}\)（スポットは遊歩道より 1 個多い）

となり、どちらも「連続区間の和」です。

素朴解がダメな理由

すべての \((l,r)\) を試すと組み合わせは \(O(N^2)\) 個あり、各区間和を計算しても最大 \(N=5\times 10^5\) なので確実に TLE します。

重要な気づき

• コスト \(C_i\) はすべて正（\(C_i \ge 1\)）なので、区間を右に広げるほどコストは単調増加します。
• よって「右端を固定したとき、条件を満たす最小の左端」を 尺取り法（two pointers） で更新できます。
• 区間和は 累積和 を使えば \(O(1)\) で求められます。

この2つを組み合わせると、全体を \(O(N)\) で解けます。

アルゴリズム

0-index に直して考えます（コードも同様です）。

• 遊歩道：\(C[0], C[1], \dots, C[N-2]\)
• スポット：\(P[0], P[1], \dots, P[N-1]\)

まず累積和を作ります：

• スポット累積和：\(\text{prefP}[k] = \sum_{i=0}^{k-1} P[i]\)（長さ \(N+1\)）
• コスト累積和：\(\text{prefC}[k] = \sum_{i=0}^{k-1} C[i]\)（長さ \(N\)）

遊歩道区間を \([l, r]\)（0-index, 両端含む）とすると

• コストは \(\text{prefC}[r+1] - \text{prefC}[l]\)
• 満足度（スポット \(l\) から \(r+1\) まで）は \(\text{prefP}[r+2] - \text{prefP}[l]\)

尺取り法で以下を行います：

1. \(l=0\) とする
2. \(r=0,1,\dots,N-2\) を右端として順に動かす
3. コスト \(\text{prefC}[r+1]-\text{prefC}[l] > B\) の間、\(l\) を増やして区間を縮める
4. 条件を満たしたら、そのときの満足度 \(\text{prefP}[r+2]-\text{prefP}[l]\) で答えを更新

コストが正なので、\(r\) を進めたときに \(l\) は戻らず、全体で各ポインタは高々 \(N\) 回しか動きません。

計算量

• 時間計算量: \(O(N)\)（尺取り法で \(l,r\) がそれぞれ最大 \(N\) 回しか動かない）
• 空間計算量: \(O(N)\)（累積和配列）

実装のポイント

• 添字対応に注意：遊歩道 \([l,r]\) に対してスポットは \([l, r+1]\) なので、満足度は \(\text{prefP}[r+2]-\text{prefP}[l]\) になります。

• 累積和配列の長さ：

  • \(\text{prefP}\) は \(N+1\)
  • \(\text{prefC}\) は \((N-1)+1 = N\)

• 制約が大きいので、Python では sys.stdin.buffer.read() を使った高速入力が有効です（提示コードはそれを実装しています）。

  ソースコード

import sys

def ints():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield num

it = ints()
N = next(it)
B = next(it)

P = [next(it) for _ in range(N)]
C = [next(it) for _ in range(N - 1)]

prefP = [0] * (N + 1)
for i, v in enumerate(P):
    prefP[i + 1] = prefP[i] + v

prefC = [0] * N  # length (N-1)+1
for i, v in enumerate(C):
    prefC[i + 1] = prefC[i] + v

ans = 0
l = 0
for r in range(N - 1):
    while prefC[r + 1] - prefC[l] > B:
        l += 1
    s = prefP[r + 2] - prefP[l]
    if s > ans:
        ans = s

print(ans)

---

この解説は gpt-5.2-high によって生成されました。