概要

お気に入りの区画 \(D\) を必ず含むように、連続する \(K\) 個の区画からなる区間を選び、美しさの合計を最大化する問題です。累積和を用いて各区間の合計を高速に求め、すべての有効な区間の中から最大値を見つけます。

考察

有効な区間の開始位置 \(l\) の範囲を特定する

区間は \(l\) 番目から \(l+K-1\) 番目までの \(K\) 個の区画です。\(l\) が満たすべき条件は次の3つです：

1. \(l \geq 1\)（左端からはみ出さない）
2. \(l + K - 1 \leq N\)、すなわち \(l \leq N - K + 1\)（右端からはみ出さない）
3. \(l \leq D \leq l + K - 1\)、すなわち \(l \leq D\) かつ \(l \geq D - K + 1\)（区画 \(D\) を含む）

これらをまとめると：

\[l_{\min} = \max(1, \, D - K + 1)\]

\[l_{\max} = \min(N - K + 1, \, D)\]

具体例：\(N = 7, K = 3, D = 4\) の場合 - \(l_{\min} = \max(1, 4 - 3 + 1) = \max(1, 2) = 2\) - \(l_{\max} = \min(7 - 3 + 1, 4) = \min(5, 4) = 4\) - よって \(l \in \{2, 3, 4\}\)、つまり区間 \([2,4], [3,5], [4,6]\) が候補です。いずれも区画 \(4\) を含んでいます。

素朴なアプローチの問題点

各 \(l\) に対して毎回 \(K\) 個の要素を足すと、1回の合計計算に \(O(K)\) かかり、候補の数も最大 \(K\) 個あるため、全体で \(O(K^2)\) となり、\(K\) が大きいと遅くなります。

累積和で高速化

累積和（prefix sum） を前計算しておけば、任意の区間の合計を \(O(1)\) で求められます。

\[\text{prefix}[i] = A_1 + A_2 + \cdots + A_i, \quad \text{prefix}[0] = 0\]

とすると、区間 \([l, l+K-1]\) の合計は：

\[A_l + A_{l+1} + \cdots + A_{l+K-1} = \text{prefix}[l+K-1] - \text{prefix}[l-1]\]

アルゴリズム

1. 配列 \(A\) の累積和 \(\text{prefix}\) を \(O(N)\) で計算する。
2. 有効な \(l\) の範囲 \([l_{\min}, l_{\max}]\) を求める。
3. \(l_{\min}\) から \(l_{\max}\) まで各 \(l\) について、\(\text{prefix}[l+K-1] - \text{prefix}[l-1]\) を計算し、その最大値を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 累積和の計算に \(O(N)\)、有効な \(l\) の探索に \(O(l_{\max} - l_{\min} + 1) \leq O(K) \leq O(N)\)
• 空間計算量: \(O(N)\)
  • 累積和配列のサイズ

実装のポイント

• \(l\) の範囲の導出を正確に行うことが重要です。条件を1つでも間違えると区画 \(D\) を含まない区間を選んだり、散歩道からはみ出す区間を選んでしまいます。

• 累積和配列は 0-indexed で prefix[0] = 0 とし、prefix[i] が \(A_1\) から \(A_i\) までの合計を表すように構成すると、区間和の計算がシンプルになります。

• 美しさが負の値をとりうるため、最大値の初期値には -float('inf') を使う必要があります。

• \(N\) が最大 \(10^6\) と大きいため、sys.stdin.read() でまとめて入力を読むことで Python でも高速に動作させています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    D = int(input_data[2])
    A = [int(input_data[3 + i]) for i in range(N)]
    
    # prefix sum
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    # l must satisfy:
    # 1 <= l, l + K - 1 <= N, l <= D <= l + K - 1
    # => l >= 1, l <= N - K + 1, l <= D, l >= D - K + 1
    l_min = max(1, D - K + 1)
    l_max = min(N - K + 1, D)
    
    best = -float('inf')
    # sum of A[l..l+K-1] = prefix[l+K-1] - prefix[l-1]
    # We can just iterate, but with prefix sums it's O(1) per query
    # Number of valid l values can be up to K which can be up to 2*10^5, so iteration is fine
    for l in range(l_min, l_max + 1):
        s = prefix[l + K - 1] - prefix[l - 1]
        if s > best:
            best = s
    
    print(best)

main()

---

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