Codeforces #242 Div2 E. Colored Jenga

やることは自明だけど実装が面倒な問題。
http://codeforces.com/contest/424/problem/E

問題

赤青緑３色のブロックで構成されたジェンガがある。

このジェンガとサイコロを使ったゲームを行う。
サイコロの目は赤と黒が１つずつ、青と緑が２つずつである。

サイコロを振ったとき、その目の色に対応するブロックをジェンガを壊さず取り除けるなら、ブロックを１つ取り除く。
取り除けないならそのまま待機する。
取り除いたブロックはジェンガのルール同様最上位に積み重ねていく。

何色のブロックもジェンガを壊さず取り除けなくなったらゲーム終了である。
ゲーム終了までにのサイコロを振る回数を最少化したい。
最適手を取ったとき、サイコロを振る最少値の期待値を答えよ。

解法

地道に状態遷移を求めて、サイコロの各色が出た場合の期待値を最少化していくだけ。
状態数を減らさないと時間が間に合わないので、それ以上ブロックを取れない段は処理対象から削除したり、左右対称な構成を同一視したりしている。

int N;
map<vector<int>, double> M[64];
int st[64],num[64];

double dodo(int top,vector<int> V) {
	int otop,i,x,y,z,ng=0;
	
	otop=top=st[top];
	sort(V.begin(),V.end());
	vector<int> VV=V;
	
	if(M[top].find(V)!=M[top].end()) return M[top][V];
	if(num[top]==3) V.push_back(top), top=0, ng=1;
	
	double ma[4]={0,1e15,1e15,1e15};
	int pre=-1;
	FOR(i,V.size()-ng) {
		if(pre==V[i]) continue;
		pre=V[i];
		x=V[i]%4;
		y=V[i]/4%4;
		z=V[i]/16;
		
		vector<int> V2=V;
		V2.erase(V2.begin()+i);
		if(x&&y&&z) {
			if(top%4==0)           ma[y]=min(ma[y], dodo(top+y*1,V2));
			if(top/4%4==0)         ma[y]=min(ma[y], dodo(top+y*4,V2));
			if(top/16==0 && top%4) ma[y]=min(ma[y], dodo(top+y*16,V2));
		}
		
		if(z&&y) {
			if(x) {
				V[i]=4+x;
				if(top%4==0)           ma[z]=min(ma[z], dodo(top+z*1,V));
				if(top/4%4==0)         ma[z]=min(ma[z], dodo(top+z*4,V));
				if(top/16==0 && top%4) ma[z]=min(ma[z], dodo(top+z*16,V));
			}
			else {
				if(top%4==0)           ma[z]=min(ma[z], dodo(top+z*1,V2));
				if(top/4%4==0)         ma[z]=min(ma[z], dodo(top+z*4,V2));
				if(top/16==0 && top%4) ma[z]=min(ma[z], dodo(top+z*16,V2));
			}
		}
		if(y&&x) {
			if(z) {
				V[i]=z+4;
				if(top%4==0)           ma[x]=min(ma[x], dodo(top+x*1,V));
				if(top/4%4==0)         ma[x]=min(ma[x], dodo(top+x*4,V));
				if(top/16==0 && top%4) ma[x]=min(ma[x], dodo(top+x*16,V));
			}
			else {
				if(top%4==0)           ma[x]=min(ma[x], dodo(top+x*1,V2));
				if(top/4%4==0)         ma[x]=min(ma[x], dodo(top+x*4,V2));
				if(top/16==0 && top%4) ma[x]=min(ma[x], dodo(top+x*16,V2));
			}
		}
		V[i]=pre;
	}
	
	int sum=1;
	if(ma[1]>=1e15) ma[1]=0, sum+=1;
	if(ma[2]>=1e15) ma[2]=0, sum+=2;
	if(ma[3]>=1e15) ma[3]=0, sum+=2;
	if(sum==6) return M[otop][VV]=0;
	M[otop][VV]=(1+ma[1]/6 + ma[2]/3 + ma[3]/3)/(1-sum/6.0);
	return M[otop][VV]=(1+ma[1]/6 + ma[2]/3 + ma[3]/3)/(1-sum/6.0);
	
}

void solve() {
	int f,i,j,k,l,x,y,x2,y2,z;
	
	cin>>N;
	string S;
	
	FOR(i,64) {
		x=i%4;
		y=i/4%4;
		z=i/16;
		st[i]=(z>x)?(x*16+y*4+z):i;
		num[i]=(x>0)+(y>0)+(z>0);
	}
	
	vector<int> V;
	FOR(i,N) {
		cin>>S;
		x=0;
		FOR(y,3) {
			if(S[y]=='R') x+=1<<(y*2);
			if(S[y]=='G') x+=2<<(y*2);
			if(S[y]=='B') x+=3<<(y*2);
		}
		if(i<N-1) V.push_back(st[x]);
	}
	_P("%.12lf\n",dodo(st[x],V));
	
}

まとめ

実装にバグがあってだいぶ手間取った。