【ABC154 D】「Dice in Line」を解く【Python3】

「1から p_i」までの目があるサイコロ N個から、隣接する K個のサイコロを選んで振ったとき、出る目の合計の期待値の最大値を求める問題です。

サイコロをそれぞれ独立に振った期待値を足し合わせれば、合計の期待値になります。

提出

n, k = map(int, input().split())
p = list(map(int, input().split()))

num_li = [0]*n

for i in range(n):
    num_li[i] = (p[i]+1)/2

num = sum(num_li[:k])
ans = num

for j in range(n-k):
    num = num-num_li[j]+num_li[j+k]
    ans = max(num, ans)

print(ans)

期待値は「(pi+1)÷2」で求めることができます。

ランダムにK個、というわけではなく、隣接するK個、ということに注意です。

最初に k個目までの期待値を足したものを出しておいて（num = sum(num_li[:k])）、一つずつずらして、合計値を計算していきます。

その中で一番大きいものが答えとなります。