TopCoder SRM 827 : Div2 Hard CoinFlipping

今回はDiv1Mediumの簡略化版。
https://community.topcoder.com/stat?c=problem_statement&pm=17496

問題

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

最大でコインを何枚表の状態にできるか。

解法

Rが12以下と小さいので、各行の反転の有無を2^R通り総当たりしよう。
各列は、反転した場合としない場合でより多くの表のコインを得られる方を取ればよい。

class CoinFlipping {
	public:
	int mostHeads(vector <string> S) {
		int H=S.size();
		int W=S[0].size();
		int mask;
		int ma=0;
		FOR(mask,1<<H) {
			int x,y;
			int pat=0;
			FOR(x,W) {
				int C[2]={};
				FOR(y,H) if(S[y][x]!='.') {
					if((S[y][x]=='H') == ((mask&(1<<y))==0)) {
						C[0]++;
					}
					else {
						C[1]++;
					}
				}
				pat+=max(C[0],C[1]);
			}
			ma=max(ma,pat);
		}
		return ma;
		
	}
}

まとめ

Div2Hardにしても簡単な気はする。