Codeforces #252 Div2 E. Valera and Number

解き方のアプローチは面白いけど、問題設定はちょっと強引か。
http://codeforces.com/contest/441/problem/E

問題

数値X,K,Pが与えられる。
ここで以下の処理をK回行う。

• 乱数を引き、P%以下の確率でXを２倍する。
• それ以外の場合、すなわち(100-P)%の確率でXを１インクリメントする。

最終的なスコアは、Xを２進数表記したとき、末尾に連続した０の数である。
最終的なスコアの期待値を求めよ。

解法

基本的にはXを２倍することでスコアが１ずつ増えていく。
しかし、１インクリメントを繰り返しても末尾に０が続く場合がある。
とはいえインクリメントは高々K回である。

ここで自力でうまく解けなかったので、Editorialを見て解答。

そこで状態として[処理回数][末尾8bit][9bit目の値][9bit目の値が上にいくつ連続するか]を持ってDPすればよい。
２倍するにしても１インクリメントするにしても、末尾8bitから繰り上がった分が9bit目に行くので、9bit目の値やその連続回数を更新していけばよい。

int X,Y,K,P;
double pp;
double dpdp[201][256][2][300];

void solve() {
	int f,i,j,k,l,x,y,z;
	
	cin>>X>>K>>P;
	pp=P/100.0;
	
	if(X<256) dpdp[0][X][0][0]=1;
	else {
		i=1;
		x=X>>8;
		y=x%2;
		x>>=1;
		while(x%2==y) i++,x>>=1;
		dpdp[0][X%256][y][i]=1;
	}
	
	FOR(i,K) {
		FOR(x,256) FOR(y,2) FOR(z,300) {
			// x2
			if(y==(x>>7)) dpdp[i+1][(x<<1)%256][y][z+1] += dpdp[i][x][y][z]*pp;
			else dpdp[i+1][(x<<1)%256][y^1][1] += dpdp[i][x][y][z]*pp;
			// add
			if(x==255 && y==0) dpdp[i+1][0][1][1] += dpdp[i][x][y][z]*(1-pp);
			else if(x==255 && y==1) dpdp[i+1][0][0][z] += dpdp[i][x][y][z]*(1-pp);
			else dpdp[i+1][x+1][y][z] += dpdp[i][x][y][z]*(1-pp);
		}
	}
	double ret=0;
	for(i=1;i<256;i++) {
		j=i;
		x=0;
		while(j%2==0) x++,j>>=1;
		FOR(y,2) FOR(z,300) ret+=x*dpdp[K][i][y][z];
	}
	FOR(z,300) {
		ret+=(z+8)*dpdp[K][0][0][z];
		ret+=8*dpdp[K][0][1][z];
	}
	_P("%.12lf\n",ret);
}

まとめ

珍しい形のDPだな。