AtCoder が提供しているABC（AtCoder Beginner Contest）289 のC問題をC++とPythonで解いてみました。ABC289は、2023年2月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Coverage（Difficulty : 396）
問題はリンク先をご覧ください。
bit全検索を使う問題です。AtCoder Problems による Difficulty は 396 でした。
解答案
すべての 2N 通りについて、それぞれ 0 から 2N-1 を対応させて調べることをbit全検索と呼びます。問題を整理してみます。
- N と M を読み込む。
- 以下を M 回繰り返す。
- Ci を読み込む。
- 集合 Si（ai,1 … ai,ci）を読み込む。
- 部分集合の和が、1 から N までの整数をすべて含む部分集合の数を解答する。
最後の行を解決するためにbit全検索を使います。0 から 2M-1 までの数は、M 個の集合のすべての部分集合に対応させることができます。
bit全検索は、Project Euler 問題18 で考え方を説明したしたので、そちらも参照していただけたらと思います。
C++ プログラム例（ABC289C）
bit全検索のコードはパターン化できます。背景色を変更しました。変数 bit が状態（部分集合）を表します（19行目）。下から i ビット目が1であれば、部分集合が Si を含むとします。部分集合が含む数を set コンテナ s に追加していきます（21-24行目）。
s のサイズが N に等しければ、解答を1つ増やします（28、29行目）。すべての部分集合について調べて、解答を出力します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> a(m);
for (int i = 0; i < m; ++i) {
int c;
cin >> c;
a[i].resize(c);
for (int j = 0; j < c; ++j) {
cin >> a[i][j];
}
}
int result = 0;
for (int bit = 1; bit < (1 << m); ++bit) {
set<int> s;
for (int i = 0; i < m; ++i) {
if ((bit & (1 << i)) != 0) {
for (auto e : a[i]) {
s.insert(e);
}
}
}
if (s.size() == n) {
++result;
}
}
cout << result << endl;
return 0;
}集合 Si を一つの整数に変換して処理するプログラムも紹介します。Si は、1 から N までの任意の数を含むため、N ビットで表すことができます。このため、Si は、ひとつの整数で表すことができます。
部分集合の和が 1 から N までの整数をすべて含むかは、Si のビットORが 2N – 1 になることに等しくなります。この考えは、ABC282 B問題の2つ目のプログラムでも紹介しました。この考えに従ったプログラムは以下となります。ポイントとなる行の背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> s(m, 0);
for (int i = 0; i < m; ++i) {
int c;
cin >> c;
for (int j = 0; j < c; ++j) {
int a;
cin >> a;
s[i] += 1 << (a - 1);
}
}
int result = 0;
for (int bit = 0; bit < (1 << m); ++bit) {
int temp = 0;
for (int i = 0; i < m; ++i) {
if ((bit & (1 << i)) != 0) {
temp |= s[i];
}
}
if (temp == (1 << n) - 1) {
++result;
}
}
cout << result << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC289C）
Python でbit全検索のコードは、「1 << i」を「i ** 2」とも書けます。C++ のコーディング例に合わせて、シフト演算を採用しました。
"""AtCoder Beginner Contest 289 C"""
n, m = map(int, input().split())
a = [[] for i in range(m)]
for i in range(m):
c = int(input())
a[i] = list(map(int, input().split()))
result = 0
for bit in range(1 << m):
s = set()
for i in range(m):
if bit & (1 << i) != 0:
for j in a[i]:
s.add(j)
if len(s) == n:
result += 1
print(result)同じように、Si を一つの整数に変換して計算するプログラムの Python 版も紹介します。
"""AtCoder Beginner Contest 289 C"""
n, m = map(int, input().split())
s = [0] * m
for i in range(m):
c = int(input())
a = list(map(int, input().split()))
for j in range(c):
s[i] += 1 << (a[j] - 1)
result = 0
for bit in range(1 << m):
temp = 0
for i in range(m):
if bit & (1 << i) != 0:
temp |= s[i]
if temp == (1 << n) - 1:
result += 1
print(result)どちらも「AC」と判定されました。
最後に
bit全検索は、計算量が $O(2^N)$ と大きいです。その代わりに問題の制約が $1 \leqq N \leqq 10$ などと小さく設定されます。ときどき出てくる手法です。
引き続き ABC の問題を紹介していきます。
