ABC154D Dice in Line

問題

https://atcoder.jp/contests/abc154/tasks/abc154_d

方針

和の期待値 = 期待値の和であるため、

各サイコロの期待値を求めて
- （これは、1/2 * (p+1) で求まる）
「サイズKの窓」をスライドさせながら、窓内にあるサイコロの期待値の和を求めることで

解を得ることができる。

ポイント

愚直に「K個のサイコロを対象とする窓」をスライドさせながら和をとる実装だと、
計算量が10^10のオーダーとなってしまい、計算が間に合わない。

そこで、窓の和を求める際に窓の中の要素を全て足すのではなく、一つ隣の窓の和との差分を計算することで、計算量を削減する。

コード

N, K = map(int,input().split())
P = list(map(int,input().split()))
P = [(p+1)/2 for p in P]
sm = sum(P[:K])  # 先頭のK個の和を計算
ans = sm  #  最大値（答え）を保存する
for i in range(N-K):
    sm = sm - P[i] + P[K+i]  # 窓をずらす
    ans = max(ans, sm)  # 最大値（答え）を更新
print (ans)