解法
- まず、各行・列に対してひっくり返す・ひっくり返さないの２通りであることを確認する(２回ひっくり返すのは０回ひっくり返すのと同じ)。
- これにより、すべての場合を調べるにはO(2^R * 2^C)の計算が必要であることを確認する。
- ヒントを見る。
- R<=10よりRについては2^Rの計算をしないとどうにもならないということを得る。
- 2^10 = 1024より現実的な数値であることを確認する。
- Rはすべての場合を調べることにしたので、あるRの状態から、最適なCの状態を高速に得る方法を探る。
- Rが固定されている場合、各列は独立しているので、それぞれの列を最大にすれば全体が最大になるということがわかる。
アルゴリズム
- 各列についてそのまま1の数を数えてみる(それをsumとおく)。ひっくり返した場合、1の数は(R-sum)となる。
- その２つのうち大きいほうがその列の最大値である。
- 列の最大値を足したものがある行のひっくり返し方の組み合わせでの最大値である。
- これをすべての行のひっくり返し方(2^R)で試したときの最大値が解である。
コード例
ビットを扱ってうまくやるのではない方法。
main関数から順番に下から上に読んでください。
とある学校のPC Celeron M 1.2GHz
cygwin gcc オプション -O3 で最終入力データ約２秒。
#include
#include
#define
int r, c;
/* 入力データそのまま */
int origin[10][10000];
/* 行裏返し適用後のデータ */
int work[10][10000];
/* これに0か1のすべての場合を入れて、originに適用し、workに入れる */
int rev_r[10];
/* 最大値 すべて終わった後解となっている */
int max = 0;
/*
行が固定された後、各列の最大値を求める。
max変数より大きくなったら更新する。
*/
void calc_max(){
int x, y;
int colcnt, sum = 0;
/* rev_rを適用 */
for(y=0; y<r; y++){ for(x=0; x<c; x++){
work[y][x] = rev_r[y] ? !origin[y][x] : origin[y][x];
} }
/* そのままの1の数かひっくり返したときの1の数(元の0の数)の大きいほうを選択 */
for(x=0; x<c; x++){
colcnt = 0;
for(y=0; y<r; y++){
colcnt += work[y][x];
}
sum += MAX(colcnt, r - colcnt);
}
max = MAX(sum, max);
}
/*
すべての組み合わせについて。
rev[ind]に0と1を入れ、それぞれについて次の添え字について再帰実行。
すべて埋め終わったらcalc_maxを呼んでその組み合わせでの最大値を計算する。
*/
void all_r(int ind){
if(ind == r){
calc_max();
return;
}
rev_r[ind] = 0;
all_r(ind + 1);
rev_r[ind] = 1;
all_r(ind + 1);
}
int main(){
int x, y;
scanf("%d%d", &r, &c);
for(y=0; y<r; y++){ for(x=0; x<c; x++){
scanf("%d", &origin[y][x]);
} }
all_r(0);
printf("%d\n", max);
return 0;
}