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

abc154d

コンテスト一覧へ

 

「1から pi」までの目があるサイコロ 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]))、一つずつずらして、合計値を計算していきます。

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

スポンサーリンク

【ABC154】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。