Typical DP Contest : J - ボール

期待値系の問題、苦手なんだけどこれ落ち着いてやれば本番でも解けたな…。
http://tdpc.contest.atcoder.jp/tasks/tdpc_ball

問題

座標0～15の整数値のいくつかに的がある。
座標xにボールを投げると、(x-1)、x、(x+1)の場所のいずれかに当確率で到達する。
すべての的を倒すまでのボールを投げる回数を答えよ。

解法

座標の範囲を見ただけでBitDPだとわかる問題。
残されたボールをbitmap表現したときの期待値を、それより小さいbitmapの期待から求める。

座標(x-1)、x、(x+1)のいずれかに的があるなら、xにボールを投げる価値があるので、その時の期待値を求める。
1<=x<=14の範囲で期待値を最小化する値を求める。

期待値の求め方は毎回戸惑うので整理しておく。
bitmapがxの時の期待とをF[x]とする。
たとえば残されたボールのbitmapが6とすると、x=1,2に的があるので、x=1にボールを投げるとする。
この場合、x=0,1,2にボールが均等に行くので期待値は以下のようになる。
F[6] = 1 + (F[6^4] + F[6^2] + F[6])/3
こんな感じでF[6]が左右に出てくるのでややこしい。整理すると
F[6] = (1 + (F[6^4] + F[6^2])/3) * 3/2
となる。ほかのbitmapでも同じような感じ。左右に同じ期待値の変数が出てもあわてないようにしないと。

int N;
double F[1000000];

void solve() {
	int f,r,i,j,k,l, x,y,z,mask=0;
	
	cin>>N;
	FOR(i,N) mask |= 1<<GETi();
	
	FOR(i,1<<17) {
		if((i & mask) != i) continue;
		if(i==0) continue;
		
		F[i]=1e9;
		
		for(j=1;j<=14;j++) {
			double aa=0;
			int pat = (i >> (j-1)) & 7;
			double f1=F[i^(1<<(j-1))];
			double f2=F[i^(1<<(j))];
			double f3=F[i^(1<<(j+1))];
			
			if(pat==0) continue;
			if(pat==7) aa = 1 + (f1+f2+f3)/3;
			if(pat==6) aa = (1 + (f2+f3)/3)*1.5;
			if(pat==5) aa = (1 + (f1+f3)/3)*1.5;
			if(pat==3) aa = (1 + (f1+f2)/3)*1.5;
			if(pat==4) aa = (1 + f3/3)*3;
			if(pat==2) aa = (1 + f2/3)*3;
			if(pat==1) aa = (1 + f1/3)*3;
			
			F[i]=min(F[i],aa);
		}
	}
	return _P("%.12lf\n",F[mask]);
}

まとめ

期待値系の苦手、これで少しは克服できると良いが…。