はじめに...
今日は、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;
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;
}
bitrep(i, n)
{
group = {};
bitset<12> bits(i);
rep(j, 12)
{
if (bits[j])
{
group.push_back(j);
}
}
flag = true;
auto lambda = [](vector<int> indexes)
{
if (A[group[indexes[0]]][group[indexes[1]]] == 0)
{
flag = false;
return;
}
};
foreach_comb(group.size(), 2, lambda);
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];
}
}
}
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()
{
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)
{
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
{
base = max(base, A[i + 1]);
}
}
ans = min(ans, cost);
};
foreach_comb(n - 1, k - 1, lambda);
cout << ans << endl;
return 0;
}
なんでC++の標準にコンビネーション関数無いんだろ、、、？
終わりに...
お疲れ様でした！
ではまた！
いい感じな下に凸のグラフなので、これの最小値を求めます！.png)
