概要

連続する \(K\) 日間の売上の平均値の最大値を求め、それを \(1000\) 倍した値の小数点以下を切り捨てた整数を出力する問題。

考察

この問題では、すべての連続する \(K\) 日間について平均売上を計算し、その最大値を求めたいです。

素朴な方法としては、すべての区間に対して売上を合計し、平均を計算する方法があります。しかし、これには \(O(N \cdot K)\) の計算量がかかり、制約 \(N, K \leq 2 \times 10^5\) のもとでは非常に時間がかかりすぎます（TLE）。

重要な気づきは、「隣接する区間同士の合計値は、端の要素の差しか変わらない」ということです。つまり、一つ前の区間の合計から、新しい日を追加し、古い日を除外することで、次の区間の合計が \(O(1)\) で求められます。これはスライディングウィンドウ（しゃくとり法の一種）と呼ばれるテクニックです。

また、平均値を求める際に浮動小数点数を使うと誤差が発生する可能性があるため、最後に1000倍して切り捨てる処理を行うことで整数演算だけで処理できます。

アルゴリズム

1. 最初の \(K\) 日の合計値 current_sum を計算し、これを max_sum の初期値とする。
2. 次の日から順番に区間を右にスライドさせながら、新しい区間の合計値を更新していく：
   • 新しい日 \(T[i]\) を加え、古い日 \(T[i - K]\) を引く。
   • 更新された current_sum が max_sum より大きければ更新する。
3. 最後に max_sum を用いて平均値を計算し、1000倍して切り捨てた値を出力する。

例えば、売上が [10, 20, 30, 40] で \(K = 2\) の場合： - 区間 [10, 20]: 合計 = 30 - 区間 [20, 30]: 合計 = 50 - 区間 [30, 40]: 合計 = 70

最大合計は 70 なので、平均は \(70 / 2 = 35\)、1000倍して切り捨てると 35000 になります。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\) （入力配列の分）

実装のポイント

• 浮動小数点演算を使わず、整数で処理すること（誤差回避）。
• 最後の1000倍して切り捨ては、(sum * 1000) // Kのように整数除算を使う。
• 入力を高速に読み込むことで、大きなケースでも時間内に収まるようにする。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    T = list(map(int, data[2:]))

    # 最初のK日間の合計
    current_sum = sum(T[:K])
    max_sum = current_sum

    # スライディングウィンドウで最大の合計を求める
    for i in range(K, N):
        current_sum += T[i] - T[i - K]
        if current_sum > max_sum:
            max_sum = current_sum

    # 平均を1000倍して切り捨て
    result = (max_sum * 1000) // K
    print(result)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。