概要

\(N\) 日間の売上データから、連続する \(K\) 日間の平均売上が最大となる期間を探し、その平均値を1000倍した値（小数点以下切り捨て）を求める問題です。

考察

平均値を最大化するには？

連続する \(K\) 日間の平均値は、「\(K\) 日間の合計値 \(\div K\)」で計算されます。ここで \(K\) は定数であるため、平均値を最大化することは、合計値を最大化することと同じです。したがって、まずは「連続する \(K\) 日間の合計の最大値」を求める方針で考えます。

素朴な方法とその限界

各開始日 \(i\)（\(1 \leq i \leq N-K+1\)）について、そこから \(K\) 日間の合計を愚直に計算すると、1つの合計を求めるのに \(O(K)\) の時間がかかります。これをすべての開始位置で行うと、全体の計算量は \(O(N \times K)\) となります。 本問題の制約は \(N, K \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、制限時間内に終わりません（TLEとなります）。

計算の工夫（スライディングウィンドウ）

隣り合う期間の合計値を比較すると、大部分の要素が重複していることがわかります。 - 1日目〜\(K\)日目の合計： \(T_1 + T_2 + \dots + T_K\) - 2日目〜\(K+1\)日目の合計： \(T_2 + T_3 + \dots + T_{K+1}\)

2日目からの合計は、1日目からの合計から 「1日目の値（\(T_1\)）を引き、新たに加わる \(K+1\) 日目の値（\(T_{K+1}\)）を足す」 だけで計算できます。 このように、範囲を1つずつずらしながら差分だけを更新する手法をスライディングウィンドウと呼びます。これを利用すれば、各ステップ \(O(1)\) で合計値を更新できるため、効率的に最大値を求めることができます。

アルゴリズム

1. 最初の \(K\) 日間の合計 current_sum を計算し、暫定の最大値 max_sum とします。
2. \(i = 0\) から \(N-K-1\) まで以下の操作を繰り返します。
   • current_sum から \(T[i]\) を引き、\(T[i+K]\) を加えます。
   • max_sum と current_sum を比較し、大きい方で max_sum を更新します。
3. 最終的な max_sum を用いて、答えを計算します。
   • 求める値は \(\lfloor (\frac{max\_sum}{K}) \times 1000 \rfloor\) です。
   • 浮動小数点の誤差を避けるため、先に 1000 倍してから \(K\) で整数除算を行う \((max\_sum \times 1000) // K\) を計算します。

計算量

• 時間計算量: \(O(N)\)
  • データの読み込みに \(O(N)\)、スライディングウィンドウによる走査に \(O(N)\) かかるため、全体で \(O(N)\) となります。
• 空間計算量: \(O(N)\)
  • 売上データ \(T\) をリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が大きいため、sys.stdin.read().split() などを用いて一括で入力を取得すると実行時間を短縮できます。

• 精度への配慮: 平均値を計算する際に float 型（小数）を使うと、非常に小さな誤差によって切り捨て結果がずれる可能性があります。本解法のように「先に 1000 倍して整数で割る」ことで、誤差のない正確な整数演算が可能です。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする（高速な入力処理）
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 全体の日数, K: 連続して選ぶ日数
    N = int(input_data[0])
    K = int(input_data[1])
    
    # T: 各日の売上データのリスト
    # input_data[2:] は T_1 から T_N までの売上データに対応
    T = list(map(int, input_data[2:]))
    
    # 最初の K 日間の売上の合計を初期値として計算
    current_sum = sum(T[:K])
    max_sum = current_sum
    
    # スライディングウィンドウを用いて、連続する K 日間の合計の最大値を求める
    # i は現在のウィンドウの開始位置のインデックス
    for i in range(N - K):
        # ウィンドウを1日分右にずらす：
        # 最も古い日の売上 T[i] を引き、新しく入る日の売上 T[i + K] を加える
        current_sum = current_sum - T[i] + T[i + K]
        # これまでの最大合計値と比較して更新
        if current_sum > max_sum:
            max_sum = current_sum
            
    # 問題の要求：平均値の最大値を1000倍し、小数点以下を切り捨てた整数を出力する
    # 平均値 = 合計 / K なので、 (合計 / K) * 1000 の小数点以下切り捨てを求める
    # これは整数演算を用いて (合計 * 1000) // K と計算できる
    # Pythonの // 演算子は正数に対して小数点以下切り捨て（床関数）として機能する
    result = (max_sum * 1000) // K
    print(result)

if __name__ == '__main__':
    solve()

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