AOJ ITP2 11_B（Enumeration of Subsets II）を解く

Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の11_B問題をC++で解いてみました。

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#11では、ビットセットIIとしてbit処理を学びます。

問題（11_B: Enumeration of Subsets II）

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

AOJ ITP2 11_B問題: Enumeration of Subsets II

bit全探索とマスク値を使い部分集合を列挙します。

考え方

11-A のプログラムをベースにします。

マスク値を与えて、マスク値が紐づく部分集合Tを含むような部分集合を列挙します。

C++ プログラム例（ITP2 11_B）

ビット個数とビット位置からマスク値を求めます（12ー19行目）。このマスク値を含む部分集合をビットAND演算によって求めます（22行目）。

11-A との差分コードの背景色を変更しておきます。

以下が、C＋＋プログラムとなります。

#include <iostream>

using namespace std;

typedef unsigned long long int ull;

int main()
{
	int n;
	cin >> n;

	ull mask = 0ULL;
	int k;
	cin >> k;
	for (int i = 0; i < k; ++i) {
		int b;
		cin >> b;
		mask = mask | (1ULL << b);
	}

	for (ull bit = 0; bit < (1ULL << n); ++bit) {
		if ((bit & mask) != mask) {
			continue;
		}
		cout << bit << ":";
		for (ull i = 0; i < n; ++i) {
			if ((bit & (1ULL << i)) != 0) {
				cout << " " << i;
			}
		}
		cout << endl;
	}

	return 0;
}

上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。

最後に

トピック#11は、ライブラリ関数に依存しないbit処理を学びます。この問題では、ビットAND演算によって、ある値がマスク値を含むか判定しました。

引き続き、ITP2 の問題を紹介していきます。