はじめに...
今日は、bit全探索5問やっていきまーす
精選100問はこちら！
10 ALDS_5_A - 総当たり
問題はこちらです！
問題文↓
数列Aと作成して欲しい数nがいくつか与えられるので、Aの中からいくつか取り出してnが作成できるかを確認してください
普通に全探索ですね！
制約がn≦20なので最大2²⁰でループできそうです
よってこれはO(2ⁿn)でクリアできます
以下のようになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "yes" : "no") using ll = long long; using ull = unsigned long long; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { // 入力. int n; cin >> n; vector<ll> A(n), B; rep(i, n) cin >> A[i]; int m; cin >> m; // bit全探索. for (int i = 0; i < (1 << n); ++i) { ll x = 0; for (int j = 0; j < n; ++j) { if (i & (1 << j)) { x += A[j]; } } B.push_back(x); } // 存在するかの探索. rep(i, m) { int x; cin >> x; cout << yesNo(count(all(B), x) != 0) << endl; } return 0; }
11 AtCoder Beginner Contest 128 C - Switches
問題はこちらです！
問題文↓
あるいくつかのスイッチが偶数個もしくは奇数個押されていたら光る電球がある 電球をすべて光らすためのスイッチのon/offは何通りあるか？
on/offっていうbit全探索っぽい感じです！
コードはこんな感じになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { int n, m; cin >> n >> m; vector<vector<int>> S(m); vector<int> P(m); rep(i, m) { int x; cin >> x; rep(j, x) { int y; cin >> y; S[i].push_back(y); } } rep(i, m) cin >> P[i]; int ans = 0; for (int i = 0; i < pow(2, n); i++) { bitset<32> B(i); bool flag = true; rep(j, S.size()) { int cnt = 0; rep(k, S[j].size()) { if (B[S[j][k] - 1]) cnt++; } if (cnt % 2 != P[j]) { flag = false; } } if (flag) { ans++; } } cout << ans << endl; return 0; }
まだ、bit全探索の基本ですね
12 AtCoder Beginner Contest 002 D - 派閥
問題はこちらです！
友達リストが与えられる できるだけ少ない(グループ内のすべての人が友達である)グループを作りたい いくつのグループが出来るか
グラフでも解けそうだと感じましたが、bit全探索します
N個のbitを用意して、グループに入れていって友達かどうかを調べ上げたら良いですね！
コードはこうなりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define bitrep(i, n) for (int i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; void recursive_comb(vector<int> indexes, int s, int rest, function<void(vector<int>)> f) { if (rest == 0) { f(indexes); } else { if (s < 0) return; recursive_comb(indexes, s - 1, rest, f); indexes[rest - 1] = s; recursive_comb(indexes, s - 1, rest - 1, f); } } void foreach_comb(int n, int k, function<void(vector<int>)> f) { vector<int> indexes(k); recursive_comb(indexes, n - 1, k, f); } vector<int> group; vector<vector<bool>> A; bool flag = true; int main() { int n, m; cin >> n >> m; int ans = 0; A.resize(n + 1, vector<bool>(n + 1, false)); // 人間関係の無向グラフを作成. rep(i, m) { // 互いに知り合いの状態. int a, b; cin >> a >> b; A[a - 1][b - 1] = true; A[b - 1][a - 1] = true; } // bit全探索で調べる. bitrep(i, n) { // groupの作成→bitが1の時groupに追加. group = {}; bitset<12> bits(i); rep(j, 12) { if (bits[j]) { group.push_back(j); } } flag = true; // groupの中に含まれる人が全員知り合いであるか. auto lambda = [](vector<int> indexes) { // Aのグループi番目が0なら友達でない. if (A[group[indexes[0]]][group[indexes[1]]] == 0) { flag = false; return; } }; // Pythonで言うところのitertools.combinations(). foreach_comb(group.size(), 2, lambda); // 全員友達だったら、ansの大きい方を取る. if (flag) { ans = max(ans, (int)group.size()); } } cout << ans << endl; return 0; }
コンビネーションを全列挙するのに、Pythonではitertools.combinationsを使えば良いのですが、C++では標準関数が無いので、誰かが作っていたものを盗みました
参照はこちらです！
13 JOI 2008 予選 5 - おせんべい
問題はこちらです！
おせんべい平面上にきれいに並べられている これを行ごと、列ごとにひっくり返すことが出来る 最大でいくつのおせんべいを表向きにすることが出来るか
制約で、行は最大10までなので、行を最大2¹⁰回ループさせて固定してしまうことを考える！
すると、で実行することが出来ます！
こんな感じになりました！
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { int h, w; cin >> h >> w; vector<vector<int>> A(h, vector<int>(w)); // 白と黒の個数だけをメモしておく. rep(i, h) { rep(j, w) { cin >> A[i][j]; } } // どの行を動かすかは固定する. vector<vector<int>> B(h, vector<int>(w)); int ans = 0; bitrep(i, h) { // コピー. copy(all(A), B.begin()); // 動かす行を反転させる. bitset<10> bits(i); rep(j, 10) { if (bits[j]) { rep(k, w) { B[j][k] = !B[j][k]; } } } // 縦に見て0が多い方を取る. int x = 0; rep(j, w) { int zero = 0; rep(k, h) { if (B[k][j] == 0) zero++; } x += max(zero, h - zero); } ans = max(ans, x); } cout << ans << endl; return 0; }
14 Square869120Contest #4 B - Buildings are Colorful!
問題はこちらです！
N個の建物がある 左から見た時、K種類の建物が階段状に見えるようにしたい ビルを1高くするのに、コストが1かかるので、最小でどれぐらいのコストがかかるか
こんな感じに考察しました！
・初めを除くどの建物を見えるようにするかをbit全探索.
・初め以外の建物で、K-1色のビルが見えれば良い.
・最大でも14C7=3432回の繰り返し.
ここでもまた、コンビネーション関数を使用しました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; void recursive_comb(vector<ll> indexes, ll s, ll rest, function<void(vector<ll>)> f) { if (rest == 0) { f(indexes); } else { if (s < 0) return; recursive_comb(indexes, s - 1, rest, f); indexes[rest - 1] = s; recursive_comb(indexes, s - 1, rest - 1, f); } } void foreach_comb(ll n, ll k, function<void(vector<ll>)> f) { vector<ll> indexes(k); recursive_comb(indexes, n - 1, k, f); } ll base; vector<ll> A; ll cost; ll ans; ll k, n; int main() { // どの建物を見えるようにするかをbit全探索. // 初め以外の建物で、K-1色のビルが見えれば良い. // 最大でも14C7=3432回の繰り返し. cin >> n >> k; A.resize(n); rep(i, n) cin >> A[i]; ans = INT64_MAX; auto lambda = [](vector<ll> indexes) { base = A[0]; cost = 0; int j = 0; rep(i, n - 1) { if (i + 1 == indexes[j] + 1) { // 0以下の場合基準を変えるだけでコストは掛からない. if (base - A[indexes[j] + 1] + 1 < 0) { base = A[indexes[j] + 1]; } else { cost += base - A[indexes[j] + 1] + 1; base = base + 1; } j++; } else { // もし、選ばれていないindexなら、基準が変わる可能性がある. // 3 5 2.なら途中の基準は5になる. base = max(base, A[i + 1]); } } ans = min(ans, cost); }; // 初めはA[0]を基準にどれをどれだけ高くするか. foreach_comb(n - 1, k - 1, lambda); cout << ans << endl; return 0; }
なんでC++の標準にコンビネーション関数無いんだろ、、、？
終わりに...
お疲れ様でした！ ではまた！
