TopCoder SRM 575 Div2 Hard TheTilesDivTwo

さてDiv2 Hard。
http://community.topcoder.com/stat?c=problem_statement&pm=12501

問題

幅W(<=47)、高さH<(<=4)のチェス盤の様に白黒市松模様のグリッドが与えられる。
ここにL字型の３マス文のブロックを埋めていく。(回転させて配置しても良い)
ここで、L字の角部分は黒マスになければならない。
また、そのうち一部は他のブロックで埋められており、L字ブロックを置けない。

このとき配置できるL字ブロックの最大数を答える。

解法

高さが高々4と小さいので、DPで左端から埋めていくことにした。
今見ているX座標における4マス分の利用可否と、一つ左のX座標における４マス分の利用可否でDPしていき、現在のX座標にL字の角部分を0～2個置いていく。

各X座標において幅２マス分のマスの状態でビットDPし、高さの半分のマスにおいて４通りのパターンを試すので、ループ回数は(W*(2^2H)*(4^(1/2)H))、計算量はO(W*2^H)程度になる。
今回はH<=4なので時間は余裕。

int dt[4][2][2]= {
	{{1,0},{0,-1}},
	{{-1,0},{0,-1}},
	{{1,0},{0,1}},
	{{-1,0},{0,1}},
};

class TheTilesDivTwo {
	public:
	
	int DP[2][16][16];
	int find(vector <string> board) {
		int x,y,cur,tar,pm,cm,pat,y1,y2,t1,t2,nm;
		int W=board[0].size(),H=board.size();
		ZERO(DP);
		
		FOR(x,W) {
			cur=x%2;
			tar=1^cur;
			
			ZERO(DP[tar]);
			// 0
			FOR(pm,1<<H) FOR(cm,1<<H) DP[tar][cm][0] = max(DP[tar][cm][0], DP[cur][pm][cm]);
			// 1
			FOR(y1,H) {
				if((x+y1)%2 || board[y1][x]=='X') continue;
				
				FOR(t1,4) {
					if(x+dt[t1][0][0]<0 || x+dt[t1][0][0]>=W) continue;
					if(y1+dt[t1][1][1]<0 || y1+dt[t1][1][1]>=H) continue;
					if(board[y1+dt[t1][0][1]][x+dt[t1][0][0]]=='X') continue;
					if(board[y1+dt[t1][1][1]][x+dt[t1][1][0]]=='X') continue;
					FOR(pm,1<<H) FOR(cm,1<<H) {
						if(cm & (1<<(y1+dt[t1][1][1]))) continue;
						if(dt[t1][0][0]<0){
							if(pm & (1<<y1)) continue;
							DP[tar][cm | (1<<y1) | (1<<(y1+dt[t1][1][1]))][0] = 
								max(DP[tar][cm | (1<<y1) | (1<<(y1+dt[t1][1][1]))][0], DP[cur][pm][cm]+1);
						}
						else {
							DP[tar][cm | (1<<y1) | (1<<(y1+dt[t1][1][1]))][(1<<y1)] = 
								max(DP[tar][cm | (1<<y1) | (1<<(y1+dt[t1][1][1]))][(1<<y1)], DP[cur][pm][cm]+1);
						}
					}
				}
			}
			FOR(y1,H) for(y2=y1+1;y2<H;y2++) {
				if((x+y1)%2 || board[y1][x]=='X') continue;
				if((x+y2)%2 || board[y2][x]=='X') continue;
				
				FOR(t1,4) FOR(t2,4) {
					if(y1+dt[t1][1][1] == y2+dt[t2][1][1]) continue; // collide
					if(x+dt[t1][0][0]<0 || x+dt[t1][0][0]>=W) continue;
					if(y1+dt[t1][1][1]<0 || y1+dt[t1][1][1]>=H) continue;
					if(board[y1+dt[t1][0][1]][x+dt[t1][0][0]]=='X') continue;
					if(board[y1+dt[t1][1][1]][x+dt[t1][1][0]]=='X') continue;
					if(x+dt[t2][0][0]<0 || x+dt[t2][0][0]>=W) continue;
					if(y2+dt[t2][1][1]<0 || y2+dt[t2][1][1]>=H) continue;
					if(board[y2+dt[t2][0][1]][x+dt[t2][0][0]]=='X') continue;
					if(board[y2+dt[t2][1][1]][x+dt[t2][1][0]]=='X') continue;
					FOR(pm,1<<H) FOR(cm,1<<H) {
						if(cm & (1<<(y1+dt[t1][1][1]))) continue;
						if(cm & (1<<(y2+dt[t2][1][1]))) continue;
						nm = cm | (1<<y1) | (1<<(y1+dt[t1][1][1])) | (1<<y2) | (1<<(y2+dt[t2][1][1]));
						
						if(dt[t1][0][0]<0 && (pm & (1<<y1))) continue;
						if(dt[t2][0][0]<0 && (pm & (1<<y2))) continue;
						
						if(dt[t1][0][0]<0 && dt[t2][0][0]<0) {
							DP[tar][nm][0] = max(DP[tar][nm][0], DP[cur][pm][cm]+2);
						}
						else if(dt[t1][0][0]<0 && dt[t2][0][0]>0) {
							DP[tar][nm][1<<y2] = max(DP[tar][nm][1<<y2], DP[cur][pm][cm]+2);
						}
						else if(dt[t1][0][0]>0 && dt[t2][0][0]<0) {
							DP[tar][nm][1<<y1] = max(DP[tar][nm][1<<y1], DP[cur][pm][cm]+2);
						}
						else {
							DP[tar][nm][(1<<y1)|(1<<y2)] = max(DP[tar][nm][(1<<y1)|(1<<y2)], DP[cur][pm][cm]+2);
						}
					}
				}
			}
		}
		
		int ma=0;
		FOR(pm,1<<H) FOR(cm,1<<H) ma=max(ma, DP[W%2][pm][cm]);
		return ma;
	}
}

まとめ

１つのX座標に２つL字ブロックを置くケースをガリガリ書いたので汚いコードになってしまった…。