aoj 0525 - Osenbei

問題

問題概要

２次元にあるビット(0, 1)を任意の縦列、横列を選び任意の回数反転させることができる。最終的に最も0が多くなる時の0の数を求めよ。

解法

この問題には「R の上限 10 は C の上限 10000 に比べて小さいことに注意せよ」と書かれていて、解法が思いつきやすい。半全列挙?を行えばいい。つまり、数が少ないのは縦の数なので、横方向でbitを反転させる。どの横方向のbitを反転させるかの選びかは全部で2^r(r<=10)通りだけである。その全ての場合において、次は縦方向について考え、半分より多いbitが1の場合反転させて、その場合の合計値を求める。これを全て(2^r通り)において行い、その中の最大値が答えとなる。
したのコードの計算量は(2^r * r * c)となる。
コード自体は、maskを0から(1 << r) - 1まで動かすことで、例えばr = 3の時、000=(0)であれば全て1~3行全て反転させず、010=(2)であれば2行のみ反転して、111=(7)であれば、1~3行全てを反転している。hantei()はposビット目が1であるかを見ている。

ミス

特になし。ヒントがなければできなかったかも。 半全列挙が有効でしたね。

コード

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

bool hantei(int mask, int pos){
    if(mask & (1 << pos))return true;
    else return false;
}
int board[11][10010];
int main(void){
    int r, c;
    while(1){
        cin >> r >> c;
        if(r == 0 && c == 0) return 0;
        rep(i, r) rep(j, c) cin >> board[i][j];
        long long ans = 0;
        for (int mask = 0; mask < (1 << r); ++mask){
            vector<int> sum(c, 0);//v[i] := i列めの0の個数
            for (int pos = 0; pos < r; ++pos){
                if(hantei(mask, pos)){//反転
                    for (int i = 0; i < c; ++i){
                        if(board[pos][i] == 1) sum[i]++;//0の数が加算
                    }
                }else{//そのまま
                    for (int i = 0; i < c; ++i){
                        if(board[pos][i] == 0) sum[i]++;
                    }
                }
            }
            long long tmp = 0;
            for (int i = 0; i < c; ++i){
                if(sum[i] < (double)r / 2.0) tmp += (r - sum[i]);
                else tmp += sum[i];
            }
            ans = max(ans, tmp);
        }
        printf("%lld\n", ans);
    }
}