概要

連続する \(K\) 日間の売上合計の最大値を求め、その平均値を1000倍して出力する問題です。スライディングウィンドウを用いて効率的に解くことができます。

考察

重要な気づき

1. 平均値の最大化 = 合計値の最大化: \(K\) 日間の平均値は「合計値 ÷ \(K\)」で計算されます。\(K\) は固定なので、平均値を最大化することは、合計値を最大化することと同じです。

2. 連続する区間の合計を求める必要がある: 連続する \(K\) 日間の選び方は全部で \(N - K + 1\) 通りあります。

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

各区間について愚直に合計を計算すると、1つの区間あたり \(O(K)\) かかり、全体で \(O((N-K+1) \times K)\) = \(O(NK)\) の計算量になります。

\(N\) と \(K\) がともに \(2 \times 10^5\) の場合、最悪で \(4 \times 10^{10}\) 回の計算が必要となり、TLE（時間超過）になってしまいます。

解決策

スライディングウィンドウという手法を使います。隣り合う区間は \(K-1\) 日分の重複があることに注目すると、前の区間の合計値から次の区間の合計値を \(O(1)\) で計算できます。

例えば \(K = 3\) の場合： - 区間1: \(T_1 + T_2 + T_3\) - 区間2: \(T_2 + T_3 + T_4\) = (区間1の合計) \(- T_1 + T_4\)

アルゴリズム

1. 最初の \(K\) 日間（\(T_1\) から \(T_K\)）の合計を計算し、current_sum と max_sum に格納
2. \(i = K\) から \(N-1\) まで順に以下を繰り返す：
   • current_sum を更新：current_sum = current_sum + T[i] - T[i-K]
   • max_sum を更新：max_sum = max(max_sum, current_sum)
3. 最終的な答えは (max_sum * 1000) // K

例: N=5, K=3, T=[10, 20, 30, 25, 15]

初期: current_sum = 10+20+30 = 60, max_sum = 60
i=3: current_sum = 60 + 25 - 10 = 75, max_sum = 75
i=4: current_sum = 75 + 15 - 20 = 70, max_sum = 75

答え: (75 * 1000) // 3 = 25000

計算量

• 時間計算量: \(O(N)\)
  • 最初の \(K\) 日間の合計計算に \(O(K)\)
  • スライディングウィンドウで \(O(N - K)\)
  • 合計で \(O(N)\)
• 空間計算量: \(O(N)\)
  • 売上データ \(T\) を保存するのに \(O(N)\)

実装のポイント

1. 整数演算で精度を保つ: 平均値を直接計算すると浮動小数点の誤差が生じる可能性があります。代わりに (max_sum * 1000) // K と計算することで、整数演算のみで正確な結果が得られます。

2. 切り捨ての実装: Pythonの // 演算子は正の整数に対して切り捨て除算を行うので、そのまま使用できます。

3. インデックスに注意: スライディングウィンドウで「新しく加える要素」と「取り除く要素」のインデックスを間違えないようにしましょう。\(i\) 番目の要素を加えるとき、取り除くのは \(i - K\) 番目の要素です。

   ソースコード

def solve():
    N, K = map(int, input().split())
    T = list(map(int, input().split()))
    
    # 最初のK日間の合計を計算
    current_sum = sum(T[:K])
    max_sum = current_sum
    
    # スライディングウィンドウで最大の合計を探す
    for i in range(K, N):
        current_sum = current_sum + T[i] - T[i - K]
        if current_sum > max_sum:
            max_sum = current_sum
    
    # 平均値の1000倍を小数点以下切り捨て
    # max_sum / K * 1000 = max_sum * 1000 // K
    result = (max_sum * 1000) // K
    
    print(result)

solve()

---

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