TopCoder SRM 827 : Div1 Medium CoinFlipping2

これは解法はすぐ思い浮かんで、後は実装をいかに簡単に済ませるかって感じだった。
https://community.topcoder.com/stat?c=problem_statement&pm=17497

問題

R*Cのグリッドのいくつかのセルに、コインが置いてあり、その表裏が指定されている。
いくつか列・行を選び、その列・行内のコインの表裏を反転させる作業を繰り返す。

表を向いたコインを指定された枚数にできるか、可能ならその反転手順を求めよ。

解法

Rが12以下と小さいので、各行の反転の有無を2^R通り総当たりしよう。
各列は、反転した場合としない場合で何枚表のコインが増えるかを考え、bitsetでDPしたのち、それを復元すればよい。

bitset<640> dp[51];


class CoinFlipping2 {
	public:
	vector <int> correctHeads(vector <string> S, int desiredCount) {
		int H=S.size();
		int W=S[0].size();
		int mask;
		FOR(mask,1<<H) {
			int C[2][50]={};
			dp[0].reset();
			dp[0][0]=1;
			int x,y;
			FOR(x,W) {
				FOR(y,H) if(S[y][x]!='.') {
					if((S[y][x]=='H') == ((mask&(1<<y))==0)) {
						C[0][x]++;
					}
					else {
						C[1][x]++;
					}
				}
				dp[x+1]=(dp[x]<<C[0][x])|(dp[x]<<C[1][x]);
			}
			
			if(dp[W][desiredCount]) {
				vector<int> ret;
				FOR(y,H) if(mask&(1<<y)) ret.push_back(y);
				int cur=desiredCount;
				for(x=W-1;x>=0;x--) {
					if(cur>=C[0][x] && dp[x][cur-C[0][x]]) {
						cur-=C[0][x];
					}
					else {
						assert(cur>=C[1][x] && dp[x][cur-C[1][x]]);
						cur-=C[1][x];
						ret.push_back(H+x);
					}
				}
				return ret;
			}
			
			
		}
		return {-1};
	}
}

まとめ

こう見るとそこまで長くもないか。