Codeforces 226D (140D) The table

問題

nxm行列aijが与えられる。
この行列に対して、

  • どれか一つの列を選びその列の項全ての正負を反転させる
  • どれか一つの行を選びその行の項全ての正負を反転させる

操作を好きなだけ行い、

  • 全ての行について、その行の項の和が0以上
  • 全ての列について、その列の項の和が0以上

になっているようにしたい。


具体的な操作をどれか一つ求めよ。
操作の回数が最小である必要はないが、同じ行または列を2度以上操作してはならない。

制約条件

n, m≦100

aij ≦100

方針

逐次改善を繰り返す。
和が負の行または列があったら、その行または列を反転させる。


この操作ができなくなったら、全ての行と列の和が負でないということであるが、
この操作は有限回で行えなくなる。


何故なら、aij全ての和は、負の行または列を反転させるごとに、
少なくとも2以上大きくなり、
なおかつΣaij≦100 * 100 * 100だからである。


したがって操作の回数はO(WH * 100)で抑えられて、
一度の操作もO(max(W, H))しかかからないので、
全体の計算量はO(max(W, H)^3 * max(|aij|))になって時間内で終了する。

ソースコード

int n, m;
int a[100][100], r[100], c[100];
bool ar[100], ac[100];

int main(){
	cin >> n >> m;
	rep(i, n) rep(j, m){
		cin >> a[i][j];
		r[i] += a[i][j];
		c[j] += a[i][j];
	}
	while(1){
		bool u = 0;
		rep(i, n) if(r[i] < 0){
			u = 1;
			ar[i] ^= 1;
			r[i] *= -1;
			rep(j, m){
				c[j] = c[j] - 2 * a[i][j];
				a[i][j] *= -1;
			}
		}
		rep(i, m) if(c[i] < 0){
			u = 1;
			ac[i] ^= 1;
			c[i] *= -1;
			rep(j, n){
				r[j] = r[j] - 2 * a[j][i];
				a[j][i] *= -1;
			}
		}
		if(!u) break;
	}
	vi vr, vc;
	rep(i, n) if(ar[i]) vr.pb(i);
	rep(i, m) if(ac[i]) vc.pb(i);
	cout << vr.size();
	rep(i, vr.size()) cout << " " << vr[i] + 1;
	cout << endl;
	
	cout << vc.size();
	rep(i, vc.size()) cout << " " << vc[i] + 1;
	cout << endl;
	
	return 0;
}