概要

連続する \(K\) 日間の売上の平均が最大となる期間を考え、その最大平均を \(1000\) 倍して小数点以下切り捨てで出力します。

考察

平均値 \(\dfrac{T_l+T_{l+1}+\cdots+T_{l+K-1}}{K}\) を最大化したいですが、\(K\) は固定なので「平均を最大化する」ことは「和 \(T_l+ \cdots +T_{l+K-1}\) を最大化する」ことと同じです。つまり、求めるべきは 長さ \(K\) の連続区間の和の最大値です。

素朴に各区間ごとに和を計算すると、区間は \(N-K+1\) 個あり、各和の計算に \(O(K)\) かかるため全体で \(O(NK)\) になります。例えば \(N=2\times 10^5, K=10^5\) のような場合は計算量が大きすぎて時間切れ（TLE）になります。

そこで、隣り合う区間の和は少しだけ変わることに注目します。
例：\(K=3\) のとき - 区間 \([1,3]\) の和が \(T_1+T_2+T_3\) - 次の区間 \([2,4]\) の和は \(T_2+T_3+T_4\)

差分を見ると、前の和から \(T_1\) を引いて \(T_4\) を足すだけで更新できます。これにより各区間の和を \(O(1)\) で更新でき、全体を \(O(N)\) にできます。

最後に、最大和を \(S\) とすると最大平均は \(\dfrac{S}{K}\) なので、求める出力は
\(\left\lfloor \dfrac{S \times 1000}{K} \right\rfloor\)
です。整数演算で (S * 1000) // K と書けば「小数点以下切り捨て」をそのまま実現できます。

アルゴリズム

1. 最初の \(K\) 日分の和 window_sum = sum(T[:K]) を計算し、max_sum に保存する。
2. \(i=K\) から \(N-1\) まで順に、
   • window_sum += T[i] - T[i-K] として、区間を1日右にずらしたときの和を更新する
     （新しく入る \(T_i\) を足し、外れる \(T_{i-K}\) を引く）
   • max_sum を更新する。
3. 答えとして (max_sum * 1000) // K を出力する。

計算量

• 時間計算量: \(O(N)\)（各要素を高々1回ずつ加減算して走査）
• 空間計算量: \(O(N)\)（入力配列 \(T\) を保持）

実装のポイント

• 平均の比較は浮動小数点を使わず、区間和の最大化に帰着すると安全で高速です。

• 出力は「\(1000\) 倍して切り捨て」なので、// を使った整数除算で正確に処理できます。

• 入力サイズが大きいので sys.stdin.readline を使うと安定して高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    T = list(map(int, input().split()))
    
    window_sum = sum(T[:K])
    max_sum = window_sum
    
    for i in range(K, N):
        window_sum += T[i] - T[i - K]
        if window_sum > max_sum:
            max_sum = window_sum
    
    print((max_sum * 1000) // K)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。