概要

円環状に並んだ配列から「連続する長さ \(M\) の区間」の和の最大値を求める問題です。
円環をそのまま扱えるように、スライディングウィンドウで開始位置をずらしながら和を更新していけば、全候補を高速に調べられます。

考察

重要な観察は次の2つです。

1. 見えるゴンドラは「円環上で連続する \(M\) 個」
   → 開始位置を \(0,1,2,\dots,N-1\) とすると、ちょうど \(N\) 通りの候補がある。

2. 隣り合う開始位置どうしでは、区間がほとんど同じ
   例えば開始位置を \(s-1\) から \(s\) に動かすと、

   • 1つ左端が抜ける
   • 1つ右端が入る
     だけなので、区間和を毎回 \(M\) 個足し直す必要がない。

---

素朴にやると、各開始位置ごとに長さ \(M\) の和を計算して
\(O(NM)\) になります。
制約は \(N \le 5 \times 10^5\) なので、最悪だと非常に大きくなり TLE です。

そこで、最初の区間和だけ \(O(M)\) で作り、あとは

[ \text{current} \leftarrow \text{current} - A[\text{out}] + A[\text{in}] ]

で更新します。これなら各開始位置あたり \(O(1)\)、全体で \(O(N)\) です。

円環の「入ってくる要素」の添字は末尾をまたぐので、
[ \text{in_idx} = (s + M - 1) \bmod N ] とすれば正しく扱えます。

アルゴリズム

1. 入力を受け取る。
2. 初期区間（開始位置 \(0\)、つまり \(A[0] \sim A[M-1]\)）の和を current とする。best = current。
3. 開始位置 \(s=1\) から \(N-1\) まで順に試す。
   • 抜ける要素の添字: out_idx = s - 1
   • 入る要素の添字: in_idx = (s + M - 1) % N
   • current += A[in_idx] - A[out_idx]
   • best = max(best, current)
4. best を出力する。

この手順で、円環上の長さ \(M\) の全区間を漏れなく一度ずつ評価できます。

計算量

• 時間計算量: \(O(N)\)
  （初期和の計算 \(O(M)\) + ループ \(O(N)\)、合わせて線形）
• 空間計算量: \(O(1)\)
  （入力配列を除く追加メモリ）

実装のポイント

• 負の値があっても問題なく動くように、初期値は best = current にする（0で初期化しない）。

• 円環の処理は % N で添字を折り返す。

• M = N の場合もそのまま正しく動く（どの開始位置でも同じ全体和になる）。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    # 初期区間 [0, M-1]
    current = sum(A[:M])
    best = current

    # 円環対応のため、開始位置を 1 から N-1 まで試す
    for s in range(1, N):
        out_idx = s - 1
        in_idx = (s + M - 1) % N
        current += A[in_idx] - A[out_idx]
        if current > best:
            best = current

    print(best)

if __name__ == "__main__":
    main()

---

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