概要

長さ \(N\) の数列から、連続する \(K\) 個の要素からなる区間のうち、必ず \(D\) 番目の要素を含み、かつその合計が最大になるものを求める問題。

考察

この問題は、単純に全探索で各区間の和を計算すると、最悪の場合 \(O(N \cdot K)\) の計算量となり、制約 \(N \leq 10^6\) では間に合いません。

重要なのは、「区間の和」を高速に計算できるようにすることです。これは累積和を使うことで解決できます。

次に、どの区間を選ぶかですが、区間の開始位置 \(l\) は以下の条件を満たす必要があります： - \(1 \leq l \leq N - K + 1\)（区間が配列からはみ出さない） - \(l \leq D \leq l + K - 1\)（区間が \(D\) 番目の要素を含む）

これを整理すると、 $\( D - K + 1 \leq l \leq D \)\( となります（1-indexed）。これを0-indexedに直すと、 \)\( \max(0, D - K + 1) \leq l \leq \min(D, N - K) \)$ となります。

この範囲内で、各 \(l\) に対応する区間和 \(A_l + A_{l+1} + \cdots + A_{l+K-1}\) を累積和を用いて \(O(1)\) で求め、その最大値を求めればよいです。

アルゴリズム

1. 入力を読み込み、\(D\) を0-indexedにする。
2. 開始位置 \(l\) の有効範囲を計算する。
3. 累積和配列を構築する。
4. 有効範囲内の各 \(l\) について、区間和を累積和から求め、最大値を更新していく。
5. 最大値を出力する。

累積和の使い方

数列 \(A\) の累積和配列 \(acc\) を以下のように定義します： $\( acc[i] = A[0] + A[1] + \cdots + A[i-1] \)\( これにより、区間 \)[l, r]\( の和は \)acc[r+1] - acc[l]$ で求められます。

計算量

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

実装のポイント

• \(D\) を0-indexedに変換することを忘れない。

• 累積和は先頭に0を追加しておくと、区間和の計算がシンプルになる。

• 開始位置の範囲が空にならないことを確認する（今回は制約により保証されている）。

  ソースコード

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    D = int(data[2])
    A = list(map(int, data[3:]))

    # 1-indexed -> 0-indexed
    D -= 1

    # 区間の開始位置 l の範囲を計算
    # l <= D <= l + K - 1 => l >= D - K + 1 and l <= D
    # また、1 <= l <= N - K + 1 (0-indexedでは 0 <= l <= N - K)
    min_l = max(0, D - K + 1)
    max_l = min(D, N - K)

    if min_l > max_l:
        # 実際には制約により存在することが保証されているのでこのケースはないが念のため
        print(-float('inf'))
        return

    # 累積和を計算
    acc = [0] + list(accumulate(A))

    max_sum = -float('inf')
    for l in range(min_l, max_l + 1):
        current_sum = acc[l + K] - acc[l]
        if current_sum > max_sum:
            max_sum = current_sum

    print(max_sum)

if __name__ == "__main__":
    main()

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