寝癖頭の解法

勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #E - おせんべい

第7回日本情報オリンピック 予選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#E - おせんべい

atcoder.jp

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#E - おせんべい
https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_e
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
  int r,c;
  cin>>r>>c;
  vector<vector<int>> s(r,vector<int>(c)),f(r,vector<int>(c));
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      cin>>s[i][j];
    }
  }
  int ans=-1;
  for(int i=0;i<(1<<r);i++){
    vector<int> bit(r);
    for(int j=0;j<r;j++){
      bit[j]=(i/(1<<j))%2;
    }
    f=s;
    vector<int> v(c,0);
    for(int j=0;j<r;j++){
      for(int k=0;k<c;k++){
        if(bit[j]){
          f[j][k]=1-f[j][k];
        }
        if(f[j][k]){
          v[k]++;
        }
      }
    }
    int num=0;
    for(int k=0;k<c;k++){
      if(v[k]*2>=r){
        num+=v[k];
      }else{
        num+=(r-v[k]);
      }
    }
    ans=max(ans,num);
  }
  cout<<ans<<endl;
  return 0;
}