Codeforces #293 Div2 D. Ilya and Escalator

Cより簡単…？
http://codeforces.com/contest/518/problem/D

問題

N人の人が並んでいる。
時間1ごとに先頭の人が確率pでエスカレータに乗る。
時間T後、エスカレータに乗った人数の期待値を答えよ。

解法

時間ごとにエスカレータに乗った人数に対応する確率を更新していく典型DP。
最後に人数を確率で重みづけ平均を取ればよい。

int N,T;
double P;
double dp[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>P>>T;
	
	dp[0][0]=1;
	FOR(i,T) {
		FOR(x,N) {
			dp[i+1][x+1]+=dp[i][x]*P;
			dp[i+1][x]+=dp[i][x]*(1-P);
		}
		dp[i+1][N]+=dp[i][N];
	}
	
	double ret=0;
	FOR(i,N+1) ret += dp[T][i]*i;
	_P("%.12lf\n",ret);
}

まとめ

かなり典型だと思うけど、なんでこれDに置いたんだろう。