概要

円形に並んだゴンドラから、連続するちょうど \(M\) 個を選んだときの美しさの合計の最大値を求める問題です。
これは「円環上の長さ \(M\) の区間の最大和」を、スライディングウィンドウで高速に求める問題です。

考察

ゴンドラは円形に並んでいるので、見える組は次のような「連続する \(M\) 個」です。

• \(1, 2, \dots, M\)
• \(2, 3, \dots, M+1\)
• …
• \(N, 1, 2, \dots\)

つまり、始点を \(1\) から \(N\) までずらした区間をすべて調べればよいことになります。

素朴な方法

各始点ごとに、長さ \(M\) の区間和を毎回最初から計算すると、

• 区間の数は \(N\) 個
• 1区間あたり \(M\) 個足す

ので、計算量は \(O(NM)\) です。

制約は \(N \le 5 \times 10^5\) なので、最悪では非常に大きくなり、間に合いません。

---

重要な気づき

隣り合う区間の和は、ほとんど同じです。

例えば、今見えている区間が

\(A_s, A_{s+1}, \dots, A_{s+M-1}\)

だとすると、次の区間は

\(A_{s+1}, A_{s+2}, \dots, A_{s+M}\)

です。
つまり、

• 左端の \(A_s\) が抜ける
• 右端の \(A_{s+M}\) が新しく入る

だけです。

したがって、前の和を使って次の和を

\(\text{次の和} = \text{今の和} - \text{抜ける値} + \text{入る値}\)

と更新できます。

これなら各区間を \(O(1)\) で更新できるので、全体で \(O(N)\) になります。

---

円形への対応

配列の末尾を超えたら先頭に戻る必要があるため、添字は

\((\text{index}) \bmod N\)

で処理します。

例えば、始点を \(s\) とすると、その区間の最後に入る要素は

\(A[(s + M - 1) \bmod N]\)

です。

---

具体例

例えば

\(N=5, M=3\)
\(A=[4, -2, 7, 1, 3]\)

とします。

最初の区間は \([4, -2, 7]\) なので和は \(9\) です。

次の区間は \([-2, 7, 1]\) なので、

\(9 - 4 + 1 = 6\)

その次は \([7, 1, 3]\) なので、

\(6 - (-2) + 3 = 11\)

さらに次は \([1, 3, 4]\)（円形なので先頭に戻る）なので、

\(11 - 7 + 4 = 8\)

このように順番に更新していけば、最大値を求められます。

アルゴリズム

1. 最初の \(M\) 個の和を計算し、これを現在の和 current とする。
2. 答え ans を current で初期化する。
3. 始点 \(s=1\) から \(N-1\) まで順に動かす。
   • 前の区間から次の区間へ移るとき、
     • 抜ける要素は A[s - 1]
     • 入る要素は A[(s + M - 1) % N]
   • よって current += A[(s + M - 1) % N] - A[s - 1]
   • ans = max(ans, current) とする。
4. ans を出力する。

この方法で、円形の全ての長さ \(M\) の区間をちょうど1回ずつ調べられます。

計算量

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

実装のポイント

• 円形なので、右端に新しく入る要素の添字は % N を使って求めます。

• 和は最大で \(M \times 10^9\) 程度になりうるため、整数型のオーバーフローに注意が必要ですが、Python では問題ありません。

• 始点を \(0\) 番目から考えると実装しやすく、コードでは

  • 最初の区間を A[0:M]

  • 次の区間の始点を s=1,2,\dots,N-1 として処理しています。

    ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N, M = data[0], data[1]
    A = data[2:2 + N]

    current = sum(A[:M])
    ans = current

    for s in range(1, N):
        current += A[(s + M - 1) % N] - A[s - 1]
        if current > ans:
            ans = current

    print(ans)

if __name__ == "__main__":
    main()

---

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