概要

この問題は、数列から長さ \(K\) の連続する部分列のうち、指定された位置 \(D\) を含むものの和の最大値を求める問題です。

考察

条件を満たす区間の開始位置 \(l\) は、\(D\) 番目の区画を含む必要があるため、\(l\) の取り得る範囲は制限されます。具体的には、\(l\) は \(D\) が区間内に収まるように \([D-K+1, D]\) の範囲（ただし数列の範囲内）に限定されます。この範囲のサイズは最大 \(K\) 程度であり、\(K\) は最大 \(N\) と同じくらい大きくなりますが、\(N\) が \(10^6\) まで大きいため、全ての可能な \(l\) について直接和を計算しても十分高速です。

アルゴリズム

1. 入力を受け取ります（\(N\), \(K\), \(D\), 数列 \(A\)）
2. \(D\) を0-indexedに変換します（\(D_{index} = D-1\)）
3. 条件を満たす開始位置 \(l\) の範囲を計算します：
   • 左端：\(\max(0, D_{index} - K + 1)\)
   • 右端：\(\min(N-K, D_{index}) + 1\)（範囲は左閉右開）
4. 累積和配列 \(\text{prefix}\) を構築します（\(\text{prefix}[i] = A_0 + A_1 + \cdots + A_{i-1}\)）
5. 可能な全ての \(l\) について、区間 \([l, l+K-1]\) の和を累積和を使って計算し、最大値を求めます

計算量

• 時間計算量: \(O(N)\)
  • 累積和の構築に \(O(N)\)
  • 区間の走査に \(O(K)\)（最大 \(O(N)\)）
• 空間計算量: \(O(N)\)
  • 累積和配列のため

実装のポイント

• 累積和を使うことで、各区間の和を \(O(1)\) で計算できます

• \(l\) の範囲を正確に計算することが重要です（境界条件に注意）

• 最大値の初期値は非常に小さい値（\(-10^{18}\)）に設定します（負の値が最大になる場合があるため）

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    N = int(data[0])
    K = int(data[1])
    D = int(data[2])
    A = list(map(int, data[3:3+N]))
    
    D_index = D - 1
    
    left_bound = max(0, D_index - K + 1)
    right_bound = min(N - K, D_index) + 1
    
    max_sum = -10**18
    prefix = [0] * (N + 1)
    for i in range(1, N + 1):
        prefix[i] = prefix[i-1] + A[i-1]
    
    for l in range(left_bound, right_bound):
        r = l + K - 1
        current_sum = prefix[r+1] - prefix[l]
        if current_sum > max_sum:
            max_sum = current_sum
            
    print(max_sum)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。