Codeforces Round #140 (Div. 1) D : The table

問題概要

H*W(H,W<100)の各マスに数字(絶対値100以下)が入っている。ある行、または列を適当に選んで符号をフリップすることによって全体の和を最大化したい。そのようなフリップの方法を出力する問題。

解法

行or列の和が負になっているところを見つけてはフリップを繰り返す。フリップの度に全体の和は増加するのでこの手順は高々2*10^6回程度で終了する。ただし最大性についてはまだ理解できていない。そんな直感に反しているわけではないけど。

acceptされたコード

const int MAX_W = 100;

int H, W;
int board[MAX_W][MAX_W];
bool flippedRow[MAX_W], flippedColumn[MAX_W];
int sumRow[MAX_W], sumColumn[MAX_W];

void init() {
	scanf("%d%d", &H, &W);
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			scanf("%d", board[i] + j);
		}
	}
}

void output() {
	int countRow = 0;
	for (int i = 0; i < H; ++i) {
		if (flippedRow[i]) {
			++countRow;
		}
	}
	int countColumn = 0;
	for (int i = 0; i < W; ++i) {
		if (flippedColumn[i]) {
			++countColumn;
		}
	}
	printf("%d ", countRow);
	for (int i = 0; i < H; ++i) {
		if (flippedRow[i]) {
			printf("%d ", i+1);
		}
	}
	puts("");
	printf("%d ", countColumn);
	for (int i = 0; i < W; ++i) {
		if (flippedColumn[i]) {
			printf("%d ", i+1);
		}
	}
	puts("");
}

void solve() {
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			sumRow[i] += board[i][j];
			sumColumn[j] += board[i][j];
		}
	}

	for (;;) {
		int r = min_element(sumRow, sumRow + H) - sumRow;
		int c = min_element(sumColumn, sumColumn + W) - sumColumn;
		if (sumRow[r] >= 0 && sumColumn[c] >= 0) {
			break;
		}
		if (sumRow[r] > sumColumn[c]) {
			sumColumn[c] *= -1;
			flippedColumn[c] ^= true;
			for (int i = 0; i < H; ++i) {
				sumRow[i] -= board[i][c];
				board[i][c] *= -1;
				sumRow[i] += board[i][c];
			}
		}
		else {
			sumRow[r] *= -1;
			flippedRow[r] ^= true;
			for (int i = 0; i < W; ++i) {
				sumColumn[i] -= board[r][i];
				board[r][i] *= -1;
				sumColumn[i] += board[r][i];
			}
		}
	}

	output();
}