AOJ : 0525 - おせんべい (Osenbei)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0525&lang=jp
日本語なので省略です

アルゴリズム

この問題のポイントは、列が10000もあるのに対し、行は10しかないところにあります。
ヒントまで書いてあります。

さて、この問題を解くためにはどうすればいいかというと、数の少ない「行」に注目します。
各行のせんべいを裏返すか裏返さないかを、再帰で決定するわけです。
これをやるだけなら O(2^n) で、この問題の場合、2^10 = 1024 程度にしかなりません。

そして、全行、裏返すか裏返さないかを決定したら、次は「列」に注目します。
さて、ここでまた全列再帰で計算すると、とてつもない計算量になってしまいます。
しかし、そんなことをしなくても、各列を裏返すか裏返さないかは、自然に決まります。

列の1の数を数えれば、裏返した後の1の数もわかります。
これによって、裏返すか裏返さないかで、どっちの方が生き残るせんべいが多いか、自然に決定できるわけです。
あとは、これを全列に対し行い、生き残ったせんべいの数を数え、最大値より大きかったら更新します。

プログラム

#include <stdio.h>

#define REP(i,n,m) for(i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

int h,w;
int ans;
int flg[10],t[10][10000];

int count(void){
  int i,j;
  int tmp, res = 0;

  rep(j,w){
    //1の数を数える
    tmp = 0;
    rep(i,h) if(flg[i] && !t[i][j] || !flg[i] && t[i][j]) tmp++;

    if(tmp < h - tmp) //j列目を裏返した方がいい
      res += h - tmp;
    else //j列目を裏返さない方がいい
      res += tmp;
  }

  return res;
}

void solve(int idx){
  int res;

  if(idx == h){
    res = count();
    if(ans < res) ans = res;
    return;
  }

  //idx行目を裏返さない
  flg[idx] = 0;
  solve(idx+1);

  //idx行目を裏返す
  flg[idx] = 1;
  solve(idx+1);
}

int main(void){
  int i,j;

  while(scanf("%d%d",&h,&w) && (h||w)){
    rep(i,h) rep(j,w) scanf("%d",&t[i][j]);
    ans = 0;
    solve(0);
    printf("%d\n",ans);
  }

  return 0;
}