Codeforces #243 Div1 B. Sereja and Table

この解法は本番でないわ…。
http://codeforces.com/contest/425/problem/B

問題

0,1で構成される行列がある。
同じ値の隣接要素同士を連結したとき、それぞれが長方形を成し、かつ中も同じ数字で埋まってるようにしたい。

行列要素を最大K個書き換えられるとき、最少何個書き換えればよいか。

解法

最小値を求める割になぜか最大値が指定されるかが一見引っかかる問題。
書き換え回数が高々K回であることを用いて分岐させる。

まず、条件を満たす行列の状態を考えてみる。
これは、行単位または列単位で値を反転させることで行列の全数字を同じにできることを示す。

この際、各行の値を全部同じにできれば、1で埋まった列を反転させれば行列全部0に出来るので、行単位の反転および要素の書き換えを用いて各行の値を同じにさせることを考える。

列数が小さい場合

列数Cが2K+1より小さい場合、各行の候補を2^C通り全部試してみればよい。
各行を反転または要素を書き換えて候補の値に一致させていく。
その際要素の書き換え回数が最少となるように反転の有無を決定していく。

そして総書き換え回数の最小値を取ればよい。

列数が大きい場合

各行の候補は、高々１行目からK個以下書き換えたものである。
よってまず各行を１行目と差が小さくなるように反転させる。
次に各列を0または1にそろえるために必要な要素書き換え回数の総和を取ればよい。

int H,W,K,ret;
int A[101][101];

void solve() {
	int f,i,j,k,l,x,y;
	int mi=0;
	cin>>H>>W>>K;
	FOR(y,H) FOR(x,W) cin>>A[y][x];
	
	if(W<=K*2+1) {
		ret=K+1;
		for(int mask=0;mask<1<<W;mask++) {
			int tot=0;
			FOR(y,H) {
				int c=0;
				FOR(x,W) c += (A[y][x]!=((mask>>x)&1));
				tot+=min(c,W-c);
			}
			ret = min(ret,tot);
		}
	}
	else {
		FOR(y,H) {
			int c=0;
			FOR(x,W) c += A[y][x]!=A[0][x];
			if(c>W-c) {
				FOR(x,W) A[y][x]^=1;
			}
		}
		ret=0;
		FOR(x,W) {
			int c=0;
			FOR(y,H) c+=A[y][x];
			ret+=min(c,H-c);
		}
	}
	
	if(ret>K) _P("-1\n");
	else _P("%d\n",ret);
}

まとめ

自分はK<=10と小さ目の制限を見て、探索の分岐回数が10回に収まるのかなーとか思ってたけど違った。
Kと行列のサイズを見て方法を分けるのね…。