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;
}