概要

長さちょうど \(K\) の連続区間のうち、「必ず区画 \(D\) を含む」ものに限定して、美しさの合計が最大となる値を求めます。

考察

重要な気づき 1：区間の開始位置 \(l\) の取り得る範囲は狭い

長さ \(K\) の区間は \([l,\, l+K-1]\) です。これが区画 \(D\) を含む条件は $\( l \le D \le l+K-1 \)\( で、これを \)l\( について解くと \)\( D-K+1 \le l \le D \)\( さらに、区間がはみ出さない条件 \)\( 1 \le l \le N-K+1 \)\( もあるので、結局 \)\( L=\max(1,\, D-K+1),\quad R=\min(D,\, N-K+1) \)\( の範囲にある \)l$ だけを調べればよいことになります。

（例）\(N=10, K=4, D=6\) のとき
\(D-K+1=3\) なので \(l \in [3,6]\)。実際、開始位置が 3,4,5,6 の区間だけが 6 を含みます。

素朴な方法がダメな理由

各 \(l\) について \(K\) 個を毎回足すと、最大で \((N-K+1)\) 回それぞれ \(K\) 加算して $\( O(NK) \)\( となり、\)N=10^6$ では到底間に合いません。

解決策：スライディングウィンドウ（尺取り）

長さ \(K\) の区間和を「1つ右にずらす」たびに、 - 新しく入る要素を足す - はみ出した要素を引く

だけで更新でき、各位置を \(O(1)\) で処理できます。これにより全体で \(O(N)\) になります。

アルゴリズム

1. 条件を満たす開始位置の範囲 \([L,R]\) を $\(L=\max(1, D-K+1),\ R=\min(D, N-K+1)\)$ で求める。
2. 配列を左から順に読みながら、長さ \(K\) の「現在の区間和」\(window\_sum\) を管理する。
   • 最初の \(K\) 個を足して最初の区間和を作る（開始位置 \(l=1\)）。
   • 以降は 1 つ進むたびに「入る値を足し、出る値を引く」。
3. 各時点での開始位置 \(l\) を計算し、\(L \le l \le R\) のときだけ答え候補として最大値を更新する。
4. 最大値を出力する。

このコードでは、出ていく値をすぐ引けるように「直近 \(K\) 個」をリングバッファ（サイズ \(K\) の配列をぐるぐる使い回す）で保持しています。これにより、全要素 \(A_1..A_N\) を保持せずに処理できます。

計算量

• 時間計算量: \(O(N)\)（各要素を一定回数の演算で処理）
• 空間計算量: \(O(K)\)（リングバッファとして直近 \(K\) 個だけ保持）

実装のポイント

• 開始位置の範囲 \([L,R]\) の計算が核心です。ここを間違えると「\(D\) を含まない区間」を混ぜたり、逆に候補を落として WA になります。

• 答えが負になり得るため、初期値を \(0\) にすると誤ることがあります。コードでは ans=None とし、最初に条件を満たす区間で初期化しています。

• \(N \le 10^6\) なので、Python では 高速入力が重要です。sys.stdin.buffer.read() + 自前パーサで高速化しています。

• 区間和は最大で \(K \cdot 10^9\) 規模になり得るため、64bit 整数で扱います（Python は任意精度ですが、バッファは array('q') を使用）。

  ソースコード

import sys
from array import array

data = sys.stdin.buffer.read()
n_data = len(data)
p = 0

def next_int():
    global p
    while p < n_data and data[p] <= 32:
        p += 1
    sign = 1
    if data[p] == 45:  # b'-'
        sign = -1
        p += 1
    num = 0
    while p < n_data:
        c = data[p]
        if c <= 32:
            break
        num = num * 10 + (c - 48)
        p += 1
    return sign * num

N = next_int()
K = next_int()
D = next_int()

L = max(1, D - K + 1)
R = min(D, N - K + 1)

buf = array('q', [0]) * K
window_sum = 0
ans = None

for i in range(1, N + 1):
    x = next_int()
    if i <= K:
        window_sum += x
        buf[i - 1] = x
        if i == K:
            l = 1
            if L <= l <= R:
                ans = window_sum
    else:
        pos = (i - 1) % K
        old = buf[pos]
        buf[pos] = x
        window_sum += x - old
        l = i - K + 1
        if L <= l <= R:
            if ans is None or window_sum > ans:
                ans = window_sum

print(ans)

---

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