第７回日本情報オリンピック 予選（オンライン） E-おせんべい

問題

E - おせんべい

考察

JOI難易度６に入りました。さすがに難しいなと思いましたが問題文中の
ヒントで
Rの上限 10は Cの上限 10000に比べて小さいことに注意せよ．
とあるのでRについてbit全探索する解法に気づきます。

Rの反転する行はbit 1のときであり0との排他的論理和をとれば
　0のとき0に　1のとき1になること
反転しない行はbit0であり1との排他的論理和をとれば
0のとき1であり1のとき0になること
から，bitの数字を反転させ!bitとの排他的論理和をとればよい
ことになります。

排他的論理和はこんなふうに実用できるのですね。

列毎の反転は反転させたときとさせないときの1のmaxをとればよく
反転させたときの値はRから引けば求められます。

bit全探索でそれぞれの合計値を求め最大の値を出力します。

提出コード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int R,C;
  cin>>R>>C;
  int d[R][C];
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      cin>>d[i][j];
    }
  }
  int maxsum=0;
  for(int k=0;k<(1<<R);k++){
    int sum=0; 
    for(int j=0;j<C;j++){
      int cnt=0;
      for(int i=0;i<R;i++){
        if(!((k & (1<<i)))^d[i][j]){
          cnt++;
        }
      }
      sum+=max(cnt,R-cnt);
    }
    //cout<<k<<" "<<sum<<endl;
    maxsum=max(maxsum,sum);
  }
  cout<<maxsum<<endl;
  return 0;
}