見出し画像

ほぼ日刊競プロ ABC154 D - Dice in Line

D - Dice in Line

問題文
N 個のサイコロが左から右に一列に並べてあります。左から i 番目のサイコロは 1 から piまでの pi​種類の目がそれぞれ等確率で出ます。
隣接する K 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めてください。

考えたこと

まず1からpiまでしか出ないサイコロの期待値を求める.
1の時=1,2の時=1.5,3の時=2.0,4の時=2.5という風になっているつまり期待値は(pi+1)/2で求めることができる.
(初項1,等差0.5の等差数列)
隣接する期待値の和の求めるために区間和を求める.
まず最初に0個からK個までの和を求める.これを仮の最大値としておく.
イメージとしてはK個の塊を1つずつずらしていく形になる.
その場合,最初に求められた期待値+新しく追加された期待値-塊の1個後ろの期待値を求めることで和を求めることができる.
max関数を使い最大値を覚えておくことで解を求めることができる

N,K=map(int,input().split())
plist = list(map(int,input().split()))
e = [0]*N
#期待値は1を初項,1/2を差とする等差数列
for i in range(N):
   e[i] = (plist[i]+1)/2
#print (e[0])
tempsum = 0
for i in range(0,K):
   tempsum+= e[i]
ans = tempsum
for i in range(K,N):
   tempsum = tempsum+e[i]-e[i-K]
   ans = max(tempsum,ans)
print (ans)

この記事が気に入ったらサポートをしてみませんか?