TopCoder SRM 600 Div1 Medium PalindromeMatrix

問題

各成分が0または1の行列Aが与えられる。
Aの行のうちrowCount個以上の行が回文であり、
Aの列のうちcolumnCount個以上の列が回文になるように、
Aの成分をいくつか書き換える。

書き換えなければならない最小の個数はいくつか、求めよ。

制約条件

Aの行、列は14以下の偶数。

方針

回文にする行は、14C7 = 3400くらいしかないので全通り試す。
以下行を固定して考える。

列をペアごとに考える。左から1行目と右から1行目、左から2行目と右から2行目……みたいに。
ペアじゃない列は独立とみてよい。

ペアの列ごとに、（回文にすると決めた行とつじつまを合わせつつ）
どちらの列も回文にしない場合のコスト
どちらかの列を回文にする場合のコスト
両方の列を回文にする場合のコスト
はunion-findを使えば簡単にO(nm)くらいの計算量で計算できる。

そしたら、0, 1, 2個回文にする場合のコストがそれぞれ求まるので、
dp[回文を作った個数] := それにかかるコスト
というテーブルを全てのペアごとに更新していくDPをすれば、
全体でcolumnCount個の列の回文を作るコストが求まる。

全体の計算量はO(2^n * nm)くらい。

ソースコード

int h, W;
vector<string> A;

int dp[2][1000], p[1000], zero[1000], one[1000];
bool use[1000];

int root(int x){
	if(p[x] == x) return x;
	return p[x] = root(p[x]);
}
void merge(int a, int b){
	a = root(a); b = root(b);
	if(a == b) return;
	p[b] = a;
	zero[a] += zero[b];
	one[a] += one[b];
}
//pos列目とW-1-pos列目のペアだけを考える
//rowであらわされるbitの行と、colであらわされるbitの列はぞれぞれ回文にする
int calc(int row, int col, int pos){
	
	rep(i, h * W){
		p[i] = i;
		zero[i] = A[i / W][i % W] == '0';
		one[i] = A[i / W][i % W] == '1';
		use[i] = 0;
	}
	rep(i, h) if(row >> i & 1){
		rep(j, W / 2) if(j == pos) merge(i * W + j, i * W + (W - 1 - j));
	}
	rep(j, W) if(col >> j & 1){
		rep(i, h / 2) merge(i * W + j, (h - 1 - i) * W + j);
	}
	int res = 0;
	rep(i, h * W) if(!use[root(i)]){
		use[root(i)] = 1;
		res += min(zero[root(i)], one[root(i)]);
	}
	return res;
}
vi solve(int bit){
	vi w;
	rep(i, W / 2){
		int l = 1 << i, r = 1 << (W - i - 1);
		w.pb(calc(bit, l | r, i));
		w.pb(min(calc(bit, l, i), calc(bit, r, i)));
		w.pb(calc(bit, 0, i));
	}
	return w;
}

class PalindromeMatrix {
	public:
	int minChange(vector <string> A, int rowCount, int columnCount) {
		::A = A;
		h = A.size(); W = A[0].size();
		int ans = inf;
		
		rep(bit, 1 << h){
			
			if(__builtin_popcount(bit) != rowCount) continue;
			
			vi w = solve(bit);
			int cur = 0, next = 1;
			
			rep(j, 1000) dp[0][j] = inf;
			dp[0][0] = 0;
			
			rep(j, w.size()){
				rep(k, 1000) dp[next][k] = inf;
				rep(k, 998){
					dp[next][k + 2] = min(dp[next][k + 2], dp[cur][k] + w[j]);
					dp[next][k + 1] = min(dp[next][k + 1], dp[cur][k] + w[j + 1]);
					dp[next][k + 0] = min(dp[next][k + 0], dp[cur][k] + w[j + 2]);
				}
				swap(cur, next);
				j += 2;
			}
			
			rep(j, 1000) if(j >= columnCount) ans = min(ans, dp[cur][j]);
			
		}
		return ans;
	}
};