概要

円形に並んだ \(N\) 個のゴンドラから連続する \(M\) 個を選び、美しさの合計を最大化する問題です。スライディングウィンドウを用いて効率的に解きます。

考察

問題の整理

ゴンドラは円形に並んでいるため、例えば \(N=5, M=3\) のとき、選べる区間は以下の \(5\) 通りです：

• \([A_1, A_2, A_3]\)
• \([A_2, A_3, A_4]\)
• \([A_3, A_4, A_5]\)
• \([A_4, A_5, A_1]\)（端をまたぐ）
• \([A_5, A_1, A_2]\)（端をまたぐ）

すべての区間について合計を求め、その最大値を出力すればよいです。

素朴なアプローチの問題点

各開始位置 \(i\)（\(N\) 通り）に対して、\(M\) 個の要素を毎回足し合わせると、計算量は \(O(N \times M)\) になります。\(N\) が最大 \(5 \times 10^5\) のとき、最悪 \(O(N^2)\) 程度になり、TLE（時間超過）の恐れがあります。

解決策：スライディングウィンドウ

ウィンドウ（区間）を1つずらすとき、新しく入る要素を足し、出ていく要素を引くだけで、次の区間の合計が \(O(1)\) で求まります。これを利用すれば全体を \(O(N)\) で処理できます。

アルゴリズム

1. 最初の区間 \([A_1, A_2, \ldots, A_M]\) の合計を計算し、current_sum とする。
2. max_sum = current_sum で初期化する。
3. 開始位置 \(i\) を \(1\) から \(N-1\) まで動かしながら、以下を繰り返す：
   • 新しく入る要素: \(A_{(i + M - 1) \bmod N}\) を current_sum に加える。
   • 出ていく要素: \(A_{i-1}\) を current_sum から引く。
   • max_sum を更新する。
4. 最終的な max_sum を出力する。

具体例

\(N=5, M=3, A=[2, -1, 4, 5, 3]\) の場合：

開始位置 \(i\)	区間	加える要素	引く要素	current_sum
0	\([2, -1, 4]\)	—	—	\(5\)
1	\([-1, 4, 5]\)	\(A_3=5\)	\(A_0=2\)	\(8\)
2	\([4, 5, 3]\)	\(A_4=3\)	\(A_1=-1\)	\(12\)
3	\([5, 3, 2]\)	\(A_0=2\)	\(A_2=4\)	\(10\)
4	\([3, 2, -1]\)	\(A_1=-1\)	\(A_3=5\)	\(4\)

最大値は \(12\) です。

計算量

• 時間計算量: \(O(N)\) — 初期区間の合計に \(O(M)\)、その後のスライドに \(O(N)\)。合わせて \(O(N)\)。
• 空間計算量: \(O(N)\) — 配列 \(A\) の格納に必要。

実装のポイント

• 円形配列の処理: 配列を2つ連結する方法もありますが、インデックスに \(\bmod N\) を使うことでメモリを節約しつつ円形を扱えます。コード中の A[(i + M - 1) % N] がこれに該当します。

• 高速な入力: \(N\) が大きいため、sys.stdin.buffer.read() を使って入力を一括で読み込み、高速化しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    # Circular: extend the array
    # Compute sliding window sum of size M over circular array
    # We can concatenate A with itself and take sliding window
    
    current_sum = sum(A[:M])
    max_sum = current_sum
    
    for i in range(1, N):
        current_sum += A[(i + M - 1) % N] - A[i - 1]
        if current_sum > max_sum:
            max_sum = current_sum
    
    print(max_sum)

main()

---

この解説は claude4.6opus-thinking によって生成されました。