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; }