atcoder ABC 314 E - Roulettesの勉強

DP atcoder

atcoder.jp

・参考
AtCoder Beginner Contest 314 - YouTube

・説明
　参考動画の実装をPythonで行った。プログラムの説明は下でコメントアウトしている。


・実装

n,m=map(int,input().split())
c=[]
p=[]
s=[]
for _ in range(n):
  l=list(map(int,input().split()))
  c.append(l[0])
  p.append(l[1])
  s.append(l[2:])


dp=[10**18 for _ in range(m+1)]
dp[0]=0

for i in range(1,m+1):
  for j in range(n):
    expect=0   #期待値
    cntk=0     #Sの中で何個0があるかカウント。
  
    for k in s[j]:

      if i-k<=0:  #このときdp[0]=0より期待値は0なのでスルー。
        continue
      
      #k=0のときは式変形する。
      if k==0:
        cntk+=1
      else:
        prob=1/p[j]        #確率
        expect+=prob*dp[i-k]     
 
    expect+=c[j]             #スロットを回すのにc[j]かかるので。
    expect*=p[j]/(p[j]-cntk) #kの分、割り算する。例えば参考動画の1:36:21秒では、p[j]=3でk=1より3/2を右辺にかけ算している。
    dp[i]=min(dp[i],expect)
   
print(dp[m])