TopCoder SRM 504 Div2 Hard Algrid

最近あまり書いてないけど、Div2 HardはSRM500まで解いて、Div1 Mediumの折り返しもだいぶ進んでます。
http://community.topcoder.com/stat?c=problem_statement&pm=11348

問題

白黒マスで構成された２次元グリッドが与えられる。
ここに、あるルールに則ってマスの色を切り替えていく(問題文参照)

切り替え完了後のグリッドの状態が与えられるとき、切り替え前のグリッドの状態のうち辞書順最小のものを答えよ。

解法

i行目の色の状態はi+1行目にしか影響しない。
よって逆にi行目の状態の候補はi+1行目を見ることで絞ることができる。

今回グリッドサイズが16x16と小さい。
よって各行iについて2^16通り行の状態を総当たりし、色切り替え後のi+1行目と矛盾しないものを選べばよい。

グリッドの一辺のサイズNに対し、O(N^2*2^N)で解ける。

class Algrid {
	public:
	int H,W;
	vector <string> makeProgram(vector <string> output) {
		int y,x,mask;
		
		H=output.size();
		W=output[0].size();
		
		vector<string> retv;
		retv.push_back(output[0]);
		FOR(y,H-1) {
			retv.push_back("");
			string u=output[y];
			FOR(mask,1<<W) {
				string os;
				FOR(x,W) os+=(mask&(1<<x))?'W':'B';
				string s=os;
				FOR(x,W-1) {
					if(u[x]=='B' && u[x+1]=='W') s[x]=s[x+1]='B';
					if(u[x]=='W' && u[x+1]=='B') s[x]=s[x+1]='W';
					if(u[x]=='B' && u[x+1]=='B') swap(s[x],s[x+1]);
				}
				if(s==output[y+1]) {
					retv[y+1]=os;
					break;
				}
			}
			if(mask==1<<W) return vector<string>();
		}
		return retv;
	}
};

まとめ

数値の制限を見てパッと2^Nでいいじゃんと思いつけて良かった。