Codeforces #199 Div2. D. Xenia and Dominoes

この回DよりEの方が正解者多いけど、自分はDはノーヒントで解けてEはノーヒントで解けなかった。
http://codeforces.com/contest/342/problem/D

問題

高さ3、幅Nのグリッドが与えられる。
そのうちいくつかのマスは利用不可である。

ここで指定された1つの空白マスを除き、1x2セル分のサイズを持つドミノを敷き詰めたい。
当然、ドミノ同士やドミノと利用不可マスは重なってはならない。
また、いずれかのドミノを1マススライドして空白マスに到達できなければならない。

条件を満たすドミノの敷き詰め方の組み合わせ数を答えよ。

解法

まず、空白セルの上下左右の隣接マスについて、どのようにドミノが配置されるかを総当たりでチェックする。
各隣接マスを含むドミノの置き方はもう1マスを上下左右どこに置くかの４通りなので、全部で4^4。
実際は元の空白マスやドミノ同士が重ならないようにすると有効な組み合わせはもっと減る。

隣接マスを含むドミノを置いたら、後はDPで組み合わせ数計算。
高さが３しかないので、各マスの利用可否をbitで持ち、左端からドミノを置いていけばよい。

int N;
string S[4];
char S2[4][10002];
ll mo=1000000007;

int pt(int x,int y) {
	if(x<0 || x>=N || y<0 || y>=3) return 1;
	if(S2[y][x]=='X') return 1;
	S2[y][x]='X';
	return 0;
}

ll dodo() {
	ll dp[10002][8];
	int x,y,ma,cm,nm;
	ZERO(dp);
	dp[0][0]=1;
	FOR(x,N) {
		cm=(S2[0][x]=='X')*4+(S2[1][x]=='X')*2+(S2[2][x]=='X');
		nm=(x==N-1)?7:((S2[0][x+1]=='X')*4+(S2[1][x+1]=='X')*2+(S2[2][x+1]=='X'));
		
		FOR(ma,8) {
			if((ma & cm) != cm) continue;
			int pm=ma^cm;
			
			if(ma==0) {
				dp[x+1][7]+=dp[x][pm]; // -- -- --
				dp[x+1][4]+=dp[x][pm]; // | --
				dp[x+1][1]+=dp[x][pm]; // -- |
			}
			else if(ma==1) {
				dp[x+1][6]+=dp[x][pm]; // -- --
				dp[x+1][0]+=dp[x][pm]; // |
			}
			else if(ma==2) dp[x+1][5]+=dp[x][pm]; // -- --
			else if(ma==4) {
				dp[x+1][3]+=dp[x][pm]; // -- --
				dp[x+1][0]+=dp[x][pm]; // |
			}
			else if(ma==3) dp[x+1][4]+=dp[x][pm];
			else if(ma==5) dp[x+1][2]+=dp[x][pm];
			else if(ma==6) dp[x+1][1]+=dp[x][pm];
			else if(ma==7) dp[x+1][0]+=dp[x][pm];
		}
		FOR(ma,8) dp[x+1][ma] %= mo;
	}
	return dp[N][0];
}

void solve() {
	int f,i,j,k,l, x,y;
	int sx,sy;
	
	cin>>N;
	FOR(i,3) cin>>S[i];
	FOR(y,3) FOR(x,N) if(S[y][x]=='O') S[y][x]='X', sy=y, sx=x;
	
	ll ret=0;
	FOR(i,4*4*4*4) {
		int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
		int LM=i%4, RM=(i/4)%4;
		int TM=(i/16)%4,BM=(i/64)%4;
		if(LM!=0 && RM!=1 && TM!=2 && BM!=3) continue;
		if(sx==0 && LM!=0) continue;
		if(sx==N-1 && RM!=0) continue;
		if(sy==0 && TM!=0) continue;
		if(sy==2 && BM!=0) continue;
		
		
		FOR(j,3) strcpy(S2[j],S[j].c_str());
		int ng=0;
		if(sx>0) ng+=pt(sx-1,sy),ng+=pt(sx-1+dx[LM],sy+dy[LM]);
		if(sx<N-1) ng+=pt(sx+1,sy),ng+=pt(sx+1+dx[RM],sy+dy[RM]);
		if(sy>0) ng+=pt(sx,sy-1),ng+=pt(sx+dx[TM],sy-1+dy[TM]);
		if(sy<2) ng+=pt(sx,sy+1),ng+=pt(sx+dx[BM],sy+1+dy[BM]);
		if(ng) continue;
		
		ret=(ret + dodo()) % mo;
	}
	_P("%d\n",ret);
}

まとめ

解法はともかく、実装が面倒だな。