Codeforces Round #284 B Name That Tune
問題概要
N種類の曲があり、それらを順番に流す。聞いている側が曲名が分かり次第流す側に伝える。
流す側は伝えられたらすぐに次の曲を流す。
各曲には認知度p[i]があり毎秒ごとにp[i]%の確率で、そこから1秒で曲名がわかる。
また、各曲の歌詞には曲名がはいっているので始めのt[i]秒聞けばすぐに曲名はわかる
最後に曲名を答えたのがT秒後となるような時のそれまでに答えた曲数の期待値を求めよ
dp[i][j]:=i番目の曲から残りj秒で答えられる曲数の期待値とすると
j < t[i]の時:
dp[i][j] = Σ(k=1,j){(dp[i+1][j-k]+1)*(1-p[i]^k-1)*p[i]}
それ以外の時:
dp[i][j] = Σ(k=1,t[i]-1){(dp[i+1][j-k]+1)*(1-p[i]^k-1)*p[i]}+(1-p[i])^(t[i]-1)*(dp[i+1][j-t[i]]+1)
となりますが愚直に計算するとO(NT^2)で間に合わないのでちょっと式変形
j < t[i]の時:
dp[i][j] = Σ(k=1,j){(dp[i+1][j-k]+1)*(1-p[i]^k-1)*p[i]}
= (dp[i+1][j-1]+1)*p[i] + Σ(k=2,j){(dp[i+1][j-k]+1)*(1-p[i]^k-1)*p[i]}
= (dp[i+1][j-1]+1)*p[i] + Σ(k=1,j-1){(dp[i+1][j-1-k]+1)*(1-p[i]^k)*p[i]}
= (dp[i+1][j-1]+1)*p[i] + dp[i][j-1]*(1-p[i])
それ以外の時:
dp[i][j]
= Σ(k=1,t[i]-1){(dp[i+1][j-k]+1)*(1-p[i]^k-1)*p[i]}+(1-p[i])^(t[i]-1)*(dp[i+1][j-t[i]]+1)
= {dp[i][j-1]-(1-p[i])^(t[i]-1)*(dp[i+1][j-1-t[i]]+1)}*(1-p[i])-(dp[i+1][j-t[i]]+1)*p[i]*(1-p[i])^(t[i]-1)+(dp[i+1][j-1]+1)*p[i]+(1-p[i])^(t[i]-1)*(dp[i+1][j-t[i]]+1)
これでO(NT)なので間に合いますね
int t[5050],N,T; double p[5050]; double dp[5050][5050]; double r[5050]; double rec(int x,int rem) { if(rem<=0||x>=N)return 0; if(dp[x][rem]!=-1)return dp[x][rem]; double res = 0; if(rem<t[x])res += (rec(x+1,rem-1)+1)*p[x]+rec(x,rem-1)*(1-p[x]); else { res = rec(x,rem-1); if(rem!=t[x])res -= r[x]*(rec(x+1,rem-t[x]-1)+1); res *= (1-p[x]); res -= (rec(x+1,rem-t[x])+1)*r[x]*p[x]; res += (rec(x+1,rem-1)+1)*p[x]; res += (rec(x+1,rem-t[x])+1)*r[x]; } return dp[x][rem]=res; } int main() { cin >> N >> T; for(int i=0;i<N;i++)cin >> p[i] >> t[i]; for(int i=0;i<N;i++)p[i]/=100.0; for(int i=0;i<N;i++)r[i]=pow(1-p[i],t[i]-1); for(int i=0;i<5050;i++)for(int j=0;j<5050;j++)dp[i][j]=-1; printf("%.12f\n",rec(0,T)); return 0; }