AtCoder

ABC289 C問題(Coverage)を解く

AtCoder_ABC289_C

AtCoder が提供しているABC(AtCoder Beginner Contest)289 のC問題をC++とPythonで解いてみました。ABC289は、2023年2月11日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Coverage(Difficulty : 396)

問題はリンク先をご覧ください。

ABC289 C問題 Coverage

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$ などと小さく設定されます。ときどき出てくる手法です。

ABC289 について、引き続き、D問題まで紹介します。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA