読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #242 Div2 E. Colored Jenga

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

問題

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

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

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

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

解法

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

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

まとめ

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

広告を非表示にする