TopCoder SRM 549 Div1 Medium MagicalHats

問題

h x wのグリッド上に帽子がいくつかある。
帽子のあるマスは'H'で、帽子のないマスは'.'である。

コインがn枚あり、それぞれの額はcoins[i]である。
帽子の中にコインを隠して、次のようなゲームをする。

先手は、まだ選んでない帽子を選ぶ。
後手は、まだ選んでいない帽子の下にあるコインを制限を満たした上で入れ替える。
その帽子をひっくり返す。

制限：
それぞれの帽子の下には高々1枚のコインが隠れる。
同じ列にあるコインの枚数と、帽子の数を足すと偶数になり、
同じ行にあるコインの枚数と、帽子の数を足すと奇数になる。

これをnumGuesses回くりかえす。

選ばれた帽子の下にあったコインを全て先手がもらえる。
先手は、もらえるお金を最大化しようとし、後手は先手がもらえるお金を最小化しようとする。

互いが最善を尽くすとき、先手が貰える額を求めよ。
コインを帽子の中に条件を満たすよう隠せないとき-1を返せ。

制約条件

h, w≦13
帽子の個数≦13

方針

後手は先手が帽子を選んでからコインを入れ替えられるので、
先手が取れるコインは額の小さい順としてよい。

なので、コインの枚数のみを得点と考え、これを最大化するゲームとなる。
先手の最大得点は、それぞれの帽子に対して
0 : 未確定
1 : ひっくり返っていてコインがあった
2 : ひっくり返っていてコインがなかった
を状態とするようなDPをすれば求まる。

帽子とコインの状態がvalidかどうかは、
最初にコインの置き方を全生成して、(13C6 = 1700通りくらいしかない）
そこから隠すコインを全生成して、テーブルに入れておくことで、
DPの中ではO(1)で判定できるようになる。

DPの状態遷移は、選ぶ帽子と、それを裏返したときの結果。
「裏返したときの結果のうち答えが小さいほう」の全部の帽子に対する最大値に更新する。
invalidな状態の得点はinfとしておけばよい。

ソースコード

const int MX = 1600000;
int n, m, hat, h, w, hx[20], hy[20];
int dp[MX], pw[21];
bool valid[MX];

int rec(int bit, int step){
	int &res = dp[bit];
	if(res >= 0) return res;
	
	if(!valid[bit]) return res = inf;
	
	int b[20] = {};
	rep(i, hat) b[hat - i - 1] = bit % 3, bit /= 3;
	
	if(step == m){
		res = 0;
		rep(i, hat) if(b[i] == 1) res++;
		return res;
	}
	
	rep(i, hat) if(b[i] == 0){
		int mn = inf;
		rep(j, 2){
			int nbit = 0;
			b[i] = j + 1;
			rep(k, hat) nbit *= 3, nbit += b[k];
			mn = min(mn, rec(nbit, step + 1));
		}
		res = max(res, mn);
		b[i] = 0;
	}
	return res;
}

class MagicalHats {
	public:
	int findMaximumReward(vector <string> board, vector <int> coins, int numGuesses) 
	{
		n = coins.size();
		h = board.size(); w = board[0].size();
		m = numGuesses;
		
		hat = 0;
		rep(i, h) rep(j, w) if(board[i][j] == 'H')
			hy[hat] = i, hx[hat++] = j;
		
		rep(i, pw[hat]) valid[i] = 0;
		rep(i, 1 << hat) if(__builtin_popcount(i) == n){
			int row[20] = {}, col[20] = {};
			rep(j, h) rep(k, w) if(board[j][k] == 'H'){
				row[j]++;
				col[k]++;
			}
			rep(j, hat) if(i & 1 << j) row[hy[j]]++, col[hx[j]]++;
			
			rep(j, 20) if(row[j] % 2 || col[j] % 2) goto FAIL;
			
			rep(j, 1 << hat){
				int bit = 0;
				rep(k, hat){
					bit *= 3;
					if(!(j & 1 << k)) continue;
					bit += (i & 1 << k) ? 1 : 2;
				}
				valid[bit] = 1;
			}
			
			FAIL:;
		}
		pw[0] = 1;
		rep(i, 20) pw[i + 1] = pw[i] * 3;
		rep(i, pw[hat]) dp[i] = -1;
		
		int ans = rec(0, 0);
		if(ans == inf) return -1;
		int sum = 0;
		sort(all(coins));
		rep(i, ans) sum += coins[i];
		
		return sum;
	}
};