AOJ ITP2 11_A（Enumeration of Subsets I）を解く

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

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

問題（11_A: Enumeration of Subsets I）

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

AOJ ITP2 11_A問題: Enumeration of Subsets I

bit全探索を使い部分集合を列挙します。

考え方

2^N 通りについて、0 から 2^N – 1 までの値を対応させて全探索を行うことをbit全探索と呼びます。

2進数のビットが立っている場所を部分集合と考えて、値を列挙します。

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

最大で18ビット使うため、32ビット整数を使います。12、14、15行目が、bit全探索のコードパターンとなります。

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

#include <iostream>

using namespace std;

typedef unsigned long long int ull;

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

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

	return 0;
}

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

最後に

ITP2 の問題は、C++ ライブラリ関数を使うことで解けるものが多かったですが、トピック#11は、ライブラリ関数に依存しないbit処理を学びます。

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