AOJ-0525 : Osenbei

問題概要

0,1がかかれたH*W(H<10,W<10^4)のボードがある。各行、各列を選んで反転かけてpopulation countを最大化する問題。

解法

各行についてどこを反転するか全探索する。各列に対しては反転するか反転しないかは大きくなるようなのを選べば良い。愚直にやるとO(2^H*H*W)だけど、前処理かけてxorで求められるようにしておくとO(2^H*W)に落ちる。

acceptされたコード

import std.stdio, std.array, std.algorithm, std.conv, core.bitop, std.string;

void main(){
	int h, w;
		for(;scanf("%d%d ", &h, &w), h;){
		auto board = new int[][](h);
		foreach(ref line; board){
			line = array(map!(to!int)(readln.chomp.split));
		}

		auto vert = new int[](w);
		foreach(i; 0..h){
			foreach(j; 0..w){
				vert[j] |= board[i][j]<<i;
			}
		}

		int ans = 0;
		foreach(bit; 0..1<<h){
			ans = max(ans, reduce!((int a, int b){return a + max(popcnt(b^bit), h - popcnt(b^bit));})(0, vert));
		}

		writeln(ans);
	}
}