【分野別　初中級者が解くべき過去問精選 100 問】を初級者がC++で解く【全探索：ビット全探索】

[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](https://qiita.com/e869120/items/eb50fdaece12be418faa)の`2-3. 分野別　初中級者が解くべき過去問精選 100 問`を初級者がC++で解いていきます。

# 所感
ビット全探索は苦手だと感じた。「ビット全探索で解いてください」と言われれば解けるが、何もなく「はいどうぞ」と問題を渡されても思いつかないだろう。コンテストなら制約からメタ読みできるとは思うが、実世界の問題を考えるときはどうすればよいのだろう。

# 全探索：ビット全探索

## [10　ALDS_5_A - 総当たり](https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja)
AIZU ONLINE JUDGE に登録していないので、後回し。

## [11　AtCoder Beginner Contest 128 C - Switches](https://atcoder.jp/contests/abc128/tasks/abc128_c)
スイッチの組み合わせをbitで表現する。あとは、各パターンにおいて電球が点灯しているかを全て調べればよい。

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

int main() {
  int N, M;
  cin >> N >> M;
  
  vector<int> k(M);
  vector<vector<int>> s(M, vector<int>(N));
  for (int i = 0; i < M; i++) {
    cin >> k.at(i);
    for (int j = 0; j < k.at(i); j++) {
      cin >> s.at(i).at(j);
    }
  }
  
  vector<int> p(M);
  for (int i = 0; i < M; i++) {
    cin >> p.at(i);
  }
  
  int ans = 0;
  for (int tmp = 0; tmp < (1 << N); tmp++) {
    bitset<10> bt(tmp); 
    bool is_ok = true;
    for (int i = 0; i < M; i++) {
      int cnt = 0;
      for (int j = 0; j < k.at(i); j++) {
        if (bt.test(N - s.at(i).at(j))) {
          cnt++;
        }
      }
      if (cnt % 2 != p.at(i)) {
        is_ok = false;
      }
    }
    if (is_ok) {
      ans++;
    }
  }
  cout << ans;
}
```
https://atcoder.jp/contests/abc128/submissions/36520026

## [12　AtCoder Beginner Contest 002 D - 派閥](https://atcoder.jp/contests/abc002/tasks/abc002_4)
難しかった。派閥に属する議員の組み合わせをbitで表現する。あとは、議員同士が知り合いかどうかを全て調べればよい。
```c++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define repeq(i, a, b) for (ll i = a; i <= b; i++)
#define rrep(i, b, a) for (ll i = b; i >= a; i--)
#define repb(i, n) for (ll i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  ll N, M;
  cin >> N >> M;
  
  vector<ll> x(M), y(M);
  vector<vector<ll>> relations(N + 1);
  rep(i, 0, M) {
    cin >> x.at(i) >> y.at(i);
    relations.at(x.at(i)).push_back(y.at(i));
    relations.at(y.at(i)).push_back(x.at(i));
  }
  
  ll ans = 0;
  rep(i, 0, pow(2, N)) {
    bitset<12> s(i);
    vector<ll> people;
    rep(j, 0, N) {
      if(s[j]==1) people.push_back(j + 1);
    }
    bool flag = true;
    ll tmp = 0;
    fore(po, people) {
      tmp++;
      vector<ll> relation = relations.at(po);
      fore(po2, people) {
        if(po == po2) continue;
        if(find(all(relation), po2) == relation.end()) flag = false;
      }
    }
    if(flag && (ans < tmp)) ans = tmp;
  }
  cout << ans << endl;
}
```
https://atcoder.jp/contests/abc002/submissions/37937212

## [13　JOI 2008 予選 5 - おせんべい](https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_e)
裏返す行の組み合わせをbitで表現する。行のbitを反転させてしまえば、各列の操作は他の列に影響を及ぼさないので、列ごとに裏返しの判断をすればよい。
```c++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define repeq(i, a, b) for (ll i = a; i <= b; i++)
#define rrep(i, b, a) for (ll i = b; i >= a; i--)
#define repb(i, n) for (ll i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  ll R, C;
  cin >> R >> C;
  
  vector<vector<ll>> senbei(R, vector<ll>(C));
  rep(i, 0, R) {
    rep(j, 0, C) {
      cin >> senbei.at(i).at(j);
    }
  }
  
  ll ans = 0;
  repb(bit, R) {
    vector<vector<ll>> senbei2 = senbei;
    rep(i, 0, R) {
      if (bit & (1<<i)) {
        rep(j, 0, C) {
          senbei2.at(i).at(j) = 1 - senbei2.at(i).at(j);
        }
      }
    }
    
    ll tmp1 = 0;
    rep(j, 0, C) {
      ll tmp2 = 0;
      rep(i, 0, R) {
        if (senbei2.at(i).at(j) == 0) tmp2++;
      }
      tmp1 += max(tmp2, R - tmp2);
    }
    ans = max(ans, tmp1);
  }
  
  cout << ans << endl;
}
```
https://atcoder.jp/contests/joi2008yo/submissions/37952156

## [14　Square869120Contest #4 B - Buildings are Colorful!](https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b)
見たい建物の組み合わせをbitで表現する(一番手前は必ず見えるので固定)。次に見える建物が手前より低ければ、高さを+1する。
```c++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define repeq(i, a, b) for (ll i = a; i <= b; i++)
#define rrep(i, b, a) for (ll i = b; i >= a; i--)
#define repb(i, n) for (ll i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  ll N, K;
  cin >> N >> K;
  
  vector<ll> a(N);
  rep(i, 0, N) cin >> a.at(i);
  
  ll ans = inf;
  repb(b, N) {
    ll tmp1 = a.at(0), tmp2 = 0;
    bitset<15> bit(b);
    if (bit.test(0) && (bit.count() == K)) {
      rep(i, 1, N) {
        if (bit.test(i)) {
          if (a.at(i) <= tmp1) {
            tmp1++;
            tmp2 += tmp1 - a.at(i);
          }
        }
        if (a.at(i) > tmp1) tmp1 = a.at(i);
      }
      ans = min(ans, tmp2);
    }
  }
  cout << ans << endl;
}
```
https://atcoder.jp/contests/s8pc-4/submissions/37970484