ICPC2012 新入生教育編おまけ1 おせんべい

C++ 競技プログラミング

前回は全探索の問題をやったので、今回は主にforループの組み合わせで数え上げる感じの応用問題です。
問題はAOJの0525: Osenbeiをやります。

0525: Osenbei

行単位、列単位でおせんべいをひっくり返して表面を最大にしよう
そんでもって最大値を答えてね、という問題


テクニックとか気をつけること

  • 全探索でいける？オーダーはどのくらい？
  • for(int i=(1<=0;i--)で行単位のひっくり返しの状態を全部表現できるよ
  • if((i>>n)&1)でnビット目に1が立っているか確認できるよ
  • RC表記がわかりにくかったらxywhで表現するといいよ
  • ひっくり返したらもとに戻す

ちょっと難しいかなと思うのはビットで状態を表現するところかな。
巡回セールスマンでビットDPするときとかに使うので慣れておくといいですね。


全探索する解答

#include <iostream>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(n) REP(i,n)
 
const int MAXH=12;
const int MAXW=10002;
bool U[MAXH][MAXW]; // おせんべいの状態
int W,H;
 
int main()
{
    while(cin>>H>>W&&(H|W))
    {
        REP(y,H) REP(x,W) cin>>U[y][x];
 
        int ans=0; for(int i=(1<<H)-1;i>=0;i--) // 縦状態のループ
        {
            REP(y,H) if((i>>y)&1) REP(x,W) U[y][x]=!U[y][x]; // 反転する
 
            int res=0; REP(x,W) // ひっくり返す前の表面とひっくり返した時の表面(裏面)の確認
            {
                int v=0; REP(y,H) v+=U[y][x]?1:0;
                res += max(v,H-v);
            }
 
            ans=max(ans,res);
 
            REP(y,H) if((i>>y)&1) REP(x,W) U[y][x]=!U[y][x]; // もとに戻す
        }
 
        cout<<ans<<endl;
    }
 
    return 0;
}