TopCoder SRM 525 Div2 Hard MagicalSquare

これは特に苦戦せず解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=11594

問題

3x3のグリッドにそれぞれ文字列が格納されているとする。
ここで、各行左から右に各セルの文字列を連結した３つの文字列rowStringsと、各列上から下に各セルの文字列を連結した３つの文字列columnStringsが与えられる。

rowStrings及びcolumnStringを再現できる、元の3x3のグリッドに格納された文字列の組み合わせ数を答えよ。

解法

3x3の9マスのうち左上4マスが決まれば、rowStrings/columnStringの中身から残りのマスも決まり、矛盾がないか判定できる。
よって最大文字列長をLとすると４マス分O(L^4)で列挙すればよい。

文字列の一致判定は事前にO(L^3)で行っておくと、４マス埋めた後の無矛盾判定がO(1)で行えるので最終的にO(L^4)で処理できる。

int ok[3][3][51][51][51];
class MagicalSquare {
	public:
	
	long long getCount(vector <string> RS, vector <string> CS) {
		ll ret=0;
		int x,y,a,b,l;
		if(RS[0].size()+RS[1].size()+RS[2].size() != CS[0].size()+CS[1].size()+CS[2].size()) return 0;
		ZERO(ok);
		FOR(x,3) FOR(y,3) {
			FOR(a,RS[x].size()+1) FOR(b,CS[y].size()+1) FOR(l,51) {
				if(a+l>RS[x].size()) break;
				if(b+l>CS[y].size()) break;
				ok[x][y][a][b][l]=(RS[x].substr(a,l)==CS[y].substr(b,l));
			}
		}
		
		int l00,l01,l10,l11;
		FOR(l00,RS[0].size()+1) for(l01=0;l01<=RS[0].size()-l00;l01++) {
			FOR(l10,RS[1].size()+1) for(l11=0;l11<=RS[1].size()-l10;l11++) {
				int l02=RS[0].size()-l00-l01;
				int l12=RS[1].size()-l10-l11;
				int l20=CS[0].size()-l00-l10;
				int l21=CS[1].size()-l01-l11;
				if(l20<0 || l21<0) continue;
				if(RS[2].size()-l20-l21 != CS[2].size()-l02-l12) continue;
				int l22=RS[2].size()-l20-l21;
				if(l22<0) continue;
				if(!ok[0][0][0][0][l00]) continue;
				if(!ok[1][0][0][l00][l10]) continue;
				if(!ok[2][0][0][l00+l10][l20]) continue;
				if(!ok[0][1][l00][0][l01]) continue;
				if(!ok[1][1][l10][l01][l11]) continue;
				if(!ok[2][1][l20][l01+l11][l21]) continue;
				if(!ok[0][2][l00+l01][0][l02]) continue;
				if(!ok[1][2][l10+l11][l02][l12]) continue;
				if(!ok[2][2][l20+l21][l02+l12][l22]) continue;
				ret++;
			}
		}
		return ret;
	}
};

まとめ

配列の引数が多くてややこしいけど、解法自体は単純。