ABC154 D - Dice in Line - あっとのTECH LOG

問題原文

問題要旨

サイコロが $N$ 個ある。サイコロ $i$ の出目は、１から $pi$ まであり、それぞれの目が等確率で出る。隣接する $K$ 個のサイコロを選んで独立に振ったとき、出る目の合計の期待値の最大値を求めよ。

$1 \leq N \leq 10^{5}$

解法

それぞれのサイコロの出目は独立に決まるので、求めるのは隣接する $K$ 個のサイコロの出目の期待値の和と言い換えていい。
あるサイコロの出目の期待値は、 $(1 + 2 + ... + p) / p = \frac{p(1 + p)}{2p} = \frac{(1 + p)}{2}$ であるから、これらを前もって計算しておく。
隣接する $K$ 個のサイコロの出目の期待値の和を高速に求めるには、累積和を使うといい。

実装

from itertools import accumulate
N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [0] + [(1 + p) / 2 for p in P]
P_acc = list(accumulate(P))

ans = 0
for i in range(1, N - K + 2):
    ans = max(ans, P_acc[i + K - 1] - P_acc[i - 1])

print(ans)

感想

しんぷる。期待値の線形性っていうのかな？