Official

C - 観覧車の眺め / View from the Ferris Wheel Editorial by admin

gemini-3-flash-thinking

概要

この問題は、円状に並んだ \(N\) 個の要素（ゴンドラの美しさ）から、連続する \(M\) 個を選んだときの合計値を最大化する問題です。

考察

1. 円形の扱い

ゴンドラが円形に並んでいるため、最後の要素（インデックス \(N-1\)）の次は最初の要素（インデックス \(0\)）に戻ります。例えば \(N=3, M=2\) の場合、選べる組は \((A_1, A_2), (A_2, A_3), (A_3, A_1)\) の 3 通りです。 このような「円環」の構造は、配列の末尾に先頭の要素をいくつか付け足して、直線の配列として扱うのが定石です。今回は連続する \(M\) 個を考えるため、末尾に先頭から \(M-1\) 個分の要素をコピーすることで、すべてのパターンの連続部分列を網羅できます。

2. 素朴な解法と課題

各開始位置 \(i\) について、そこから \(M\) 個の合計を愚直に計算すると、1 つの合計を求めるのに \(O(M)\) かかります。これを \(N\) 箇所の開始位置すべてで行うと、全体の計算量は \(O(N \times M)\) となります。 本問題の制約は \(N, M \leq 5 \times 10^5\) であるため、最大で \(2.5 \times 10^{11}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

3. 計算の効率化（スライディングウィンドウ）

隣り合う「連続する \(M\) 個の区間」を比較すると、ほとんどの要素が共通していることに注目します。 - 区間 1: \([A_0, A_1, \dots, A_{M-1}]\) - 区間 2: \([A_1, A_2, \dots, A_M]\)

区間 1 の合計から区間 2 の合計を求めるには、「先頭の \(A_0\) を引き、末尾の \(A_M\) を足す」だけで済みます。この手法はスライディングウィンドウと呼ばれ、各ステップを \(O(1)\) で計算できるようになります。

アルゴリズム

  1. 配列 \(A\) の末尾に \(A\) の先頭 \(M-1\) 個の要素を連結した、長さ \(N+M-1\) の拡張配列を作成します。
  2. 最初の \(M\) 個の合計 curr_sum を計算し、暫定の最大値 max_sum とします。
  3. ウィンドウを 1 つずつ右にずらしていきます。
    • curr_sum から「ウィンドウから外れる左端の要素」を引き、「新しく入る右端の要素」を足します。
    • max_sum を curr_sum と比較して更新します。
  4. 最終的な max_sum を出力します。

計算量

  • 時間計算量: \(O(N)\)
    • 入力の読み込みに \(O(N)\)、最初の合計計算に \(O(M)\)、ウィンドウの移動（\(N-1\) 回）に \(O(N)\) かかります。\(M \leq N\) なので全体で \(O(N)\) です。
  • 空間計算量: \(O(N)\)
    • 長さ \(N+M-1\) の配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

  • 高速な入出力: \(N\) が大きいため、Python では sys.stdin.read().split() を使って一括で入力を読み込むことで、実行時間を短縮しています。

  • 負の数への対応: 美しさ \(A_i\) には負の値が含まれる可能性があります。初期の最大値は 0 ではなく、必ず最初のウィンドウの合計値で初期化するようにします。

  • 特殊なケース: \(M=N\) の場合は、どの位置から見ても全ゴンドラの合計値になるため、そのまま合計を出力して終了しても問題ありません。”`markdown

    概要

    この問題は、円状に並んだ \(N\) 個の要素（ゴンドラの美しさ）から、連続する \(M\) 個を選んだときの合計値を最大化する問題です。

考察

1. 円形の扱い

ゴンドラが円形に並んでいるため、最後の要素（インデックス \(N-1\)）の次は最初の要素（インデックス \(0\)）に戻ります。例えば \(N=3, M=2\) の場合、選べる組は \((A_1, A_2), (A_2, A_3), (A_3, A_1)\) の 3 通りです。 このような「円環」の構造は、配列の末尾に先頭の要素をいくつか付け足して、直線の配列として扱うのが定石です。今回は連続する \(M\) 個を考えるため、末尾に先頭から \(M-1\) 個分の要素をコピーすることで、すべてのパターンの連続部分列を網羅できます。

2. 素朴な解法と課題

各開始位置 \(i\) について、そこから \(M\) 個の合計を愚直に計算すると、1 つの合計を求めるのに \(O(M)\) かかります。これを \(N\) 箇所の開始位置すべてで行うと、全体の計算量は \(O(N \times M)\) となります。 本問題の制約は \(N, M \leq 5 \times 10^5\) であるため、最大で \(2.5 \times 10^{11}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

3. 計算の効率化（スライディングウィンドウ）

隣り合う「連続する \(M\) 個の区間」を比較すると、ほとんどの要素が共通していることに注目します。 - 区間 1: \([A_0, A_1, \dots, A_{M-1}]\) - 区間 2: \([A_1, A_2, \dots, A_M]\)

区間 1 の合計から区間 2 の合計を求めるには、「先頭の \(A_0\) を引き、末尾の \(A_M\) を足す」だけで済みます。この手法はスライディングウィンドウと呼ばれ、各ステップを \(O(1)\) で計算できるようになります。

アルゴリズム

  1. 配列 \(A\) の末尾に \(A\) の先頭 \(M-1\) 個の要素を連結した、長さ \(N+M-1\) の拡張配列を作成します。
  2. 最初の \(M\) 個の合計 curr_sum を計算し、暫定の最大値 max_sum とします。
  3. ウィンドウを 1 つずつ右にずらしていきます。
    • curr_sum から「ウィンドウから外れる左端の要素」を引き、「新しく入る右端の要素」を足します。
    • max_sum を curr_sum と比較して更新します。
  4. 最終的な max_sum を出力します。

計算量

  • 時間計算量: \(O(N)\)
    • 入力の読み込みに \(O(N)\)、最初の合計計算に \(O(M)\)、ウィンドウの移動（\(N-1\) 回）に \(O(N)\) かかります。\(M \leq N\) なので全体で \(O(N)\) です。
  • 空間計算量: \(O(N)\)
    • 長さ \(N+M-1\) の配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

  • 高速な入出力: \(N\) が大きいため、Python では sys.stdin.read().split() を使って一括で入力を読み込むことで、実行時間を短縮しています。

  • 負の数への対応: 美しさ \(A_i\) には負の値が含まれる可能性があります。初期の最大値は 0 ではなく、必ず最初のウィンドウの合計値で初期化するようにします。

  • 特殊なケース: \(M=N\) の場合は、どの位置から見ても全ゴンドラの合計値になるため、そのまま合計を出力して終了しても問題ありません。

    ソースコード

import sys

def solve():
    # 高速な入力読み込みのためにsys.stdin.read().split()を使用
    # これにより、すべてのトークンを一度に読み込み、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: ゴンドラの数, M: 見えるゴンドラの数
    n = int(input_data[0])
    m = int(input_data[1])
    
    # ゴンドラの美しさのリスト
    # mapを使用することで、大量の数値を高速に整数型に変換します
    a = list(map(int, input_data[2:]))
    
    # 全てのゴンドラが見える場合は、合計値は常に一定です
    if m == n:
        print(sum(a))
        return
    
    # 円形の並びを考慮するために、リストを拡張します
    # 連続するM個のゴンドラの開始位置は 0, 1, ..., N-1 の N 通りあります。
    # 開始位置が N-1 のとき、終了位置は (N-1) + (M-1) となるため、
    # インデックス N+M-2 までの要素が必要です。
    a_ext = a + a[:m-1]
    
    # 最初の窓（インデックス 0 から M-1）の合計を計算
    curr_sum = sum(a[:m])
    max_sum = curr_sum
    
    # スライディングウィンドウを用いて、他のすべての開始位置（1 から N-1）について合計を求めます
    # 各ステップで、窓の左端の要素を引き、右側に新しく入る要素を足すことで
    # 効率的に（O(1)で）次の窓の合計を計算できます。
    for i in range(n - 1):
        # i は現在の窓から除外される要素のインデックス
        # i + m は新しく窓に追加される要素のインデックス
        curr_sum += a_ext[i + m] - a_ext[i]
        if curr_sum > max_sum:
            max_sum = curr_sum
            
    # 最大の合計値を出力
    print(max_sum)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。