TopCoder SRM 549 Div1 Medium MagicalHats

SRM549は記念すべきDiv1初参加の回。
この回はMedium600ptだったし、案の定解けませんでした。
http://community.topcoder.com/stat?c=problem_statement&pm=11966

問題

2次元グリッド上のN個のセルに帽子がある。
これら帽子とC個のコインで以下のゲームを行う。

プレイヤーがどこかの帽子を選択すると、そのあとでゲームマスターは帽子にコインを隠す。
この際以下のルールを守るように隠す。

• オープンな帽子にはそれ以上コインを隠せない。
• オープンでない帽子には、1個だけコインを隠すことができる。
• 各列または行における帽子＋コインの数が偶数でなければならない。

その後プレイヤーが指定した帽子をオープンし、帽子の中にコインがあるとコインはプレイヤーのものとなる。
なお、その際オープンした帽子と中のコインは以後動かすことができない。

プレイヤーは最大K回まで帽子をオープンできる。
プレイヤーは総コインの価値を最大化し、ゲームマスターは最小化しようとするとき、得られる総価値を最大化せよ。

解法

N<=13なので、bitmaskで帽子のオープン/クローズ状態及びコインの有無の計2^(2N)パターンをDFSで探索し、遷移可能な状態をたどりつつ得られるコインの枚数を最大化すればよい。
得られるコインの最大数がわかれば、後は価値の低い順に子院を得られる。

DFSでは気を付けないとTLEするので、ちゃんと事前計算などして枝刈りしないとダメ。

class MagicalHats {
public:
	int N,CO,NG;
	vector<int> ok;
	map<pair<int,int>,int > vis;
	
	int dfs(int mask1,int mask2) {
		int i;
		if(vis.find(make_pair(mask1,mask2))!=vis.end()) return vis[make_pair(mask1,mask2)];
		
		
		if(__builtin_popcount(mask1)==NG) return vis[make_pair(mask1,mask2)]=__builtin_popcount(mask1&mask2);
		
		int ma=0;
		FOR(i,N) if((mask1&(1<<i))==0) {
			int sel[2]={0,0};
			ITR(it,ok) if((*it & mask1)==mask2 && ((*it&(1<<i))==0)) sel[0]=1;
			ITR(it,ok) if((*it & mask1)==mask2 && ((*it&(1<<i))>0)) sel[1]=1;
			if(sel[0]&&sel[1]) ma=max(ma,min(dfs(mask1|(1<<i),mask2|(1<<i)),dfs(mask1|(1<<i),mask2)));
			else if(sel[0]) ma=max(ma,dfs(mask1|(1<<i),mask2));
			else if(sel[1]) ma=max(ma,dfs(mask1|(1<<i),mask2|(1<<i)));
		}
		return vis[make_pair(mask1,mask2)]=ma;
	}
	
	int findMaximumReward(vector <string> board, vector <int> coins, int numGuesses) {
		int i,x,y,mask,mask2;
		int H=board.size(),W=board[0].size();
		int X[13],Y[13],R[13],C[13];
		
		NG=numGuesses;
		CO=coins.size();
		N=0;
		FOR(y,H) FOR(x,W) if(board[y][x]=='H') X[N]=x,Y[N]=y,N++;
		ok.clear();
		
		FOR(mask,1<<N) 	if(__builtin_popcount(mask)==CO) {
			ZERO(R);
			ZERO(C);
			FOR(i,N) if((mask&(1<<i))==0) R[Y[i]]^=1,C[X[i]]^=1;
			x=1;
			FOR(i,13) if(R[i]|C[i]) x=0;
			if(x) ok.push_back(mask);
		}
		if(ok.empty()) return -1;
		
		vis.clear();
		x=dfs(0,0);
		
		int ret=0;
		sort(coins.begin(),coins.end());
		FOR(i,x) ret+=coins[i];
		return ret;
	}
}

まとめ

やるべきことは割と明確だけど、とかくbitmaskの管理が面倒な問題。
コードを最初書いてから通すまでだいぶ手間取った。