Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-08-04SRM478 Div1

ビットによる部分集合の列挙

| 01:02 | ビットによる部分集合の列挙 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - ビットによる部分集合の列挙 - SRM diary(Sigmar) ビットによる部分集合の列挙 - SRM diary(Sigmar) のブックマークコメント

SRM478 Div1 500のように、ビットDPを使うときなどに、ある集合(maskとする)の全ての部分集合を列挙したい場合があります。

(maskは整数値、maskのビット数はn、maskのビットのうち1が立っているところをmaskが表す集合の要素とみなします。また、maskの部分集合をiで表します。)

この場合、iを0から2^n-1まで全部列挙してmaskの部分集合となっている場合のみ評価するというやり方だと、計算量が多くなってしまうので、ビット論理積とデクリメントを使って本当にmaskの部分集合のみを列挙する方法があります。

ただしこの方法は気をつけないと無限ループになったり注意が必要なので少しまとめておきたいと思います。


例えば、mask=100101とすると、その部分集合である000000, 000001, 000100, 000101, 100000, 100001, 100100, 100101を列挙するのが今回の目的です。


何となくのやり方は、TopcoderのAlgorithm TutorialのAll the subsetsの欄を見てください。


1. maskの部分集合を列挙する

	a. i==0を評価しない
		for(int i=mask; i>0; i=(i-1)&mask) {
		}
	b. i==0を評価する
		for(int i=mask; i>=0; i--) {
			i&=mask;
		}

i==0を評価する(for文の継続条件をi>=0とする)とき、1.aのようにfor文の更新文の中でmaskとビット論理積を取ると、いつまで経ってもiが負の値にならず、無限ループします。

また、i==0を評価しない(for文の継続条件をi>0とする)場合、1.bのようにfor文の次の文でmaskとビット論理積をとると、i==0を評価してしまい意図した結果になりません。(1.aの書き方にするなり、break文を入れるなりしましょう)


2. maskを含む集合を列挙する

少し目的は変わりますが同じようなやり方でできる処理が、maskを含む集合の列挙です。

	for(int i=mask; i<(1<<n); i=(i+1)|mask) {
	}

なお初期値をmaskでなく0にすると、i==maskの値を評価できない場合があるため避けたほうが良いと思います。


1.aを用いたビットDP(メモ化)の例(擬似コード)です。

int memo[1<<n];
int rec(int mask) {
	int res=init;
	if(mask==0) return init;
	if(memo[mask]>=0) return memo[mask];
	for(int i=mask; i>0; i=(i-1)&mask) {
		res=best(res, calc(rec(mask^i), i));
	}
	memo[mask]=res;
	return res;
}

このようなDPの場合、計算量はmaskのビットが1のときのみiのビットを0か1から選ぶため、ビット単位で考えると(mask:0,i:0), (mask:1,i:0), (mask:1,i:1)の3通りをビット数分累乗したパターンの計算で3^nの計算量となります。


誤り等ありましたらご指摘くださいませ。