Problem 201 「唯一の和を持つ部分集合」 †
変更履歴
(*2013/12/10 らすかるさんというかたから計算方法に記述ミスがあると指摘を受け修正、まだ解説サイトを始めたばかりで不慣れなためにこういうミスは減らさねばとよい自戒となる、１２月１１日図の修正完了)
(*2013/12/13 図の説明のＢｉｔが１桁ずれていること一部の解説がわかりにくいことをaerile_reさんという方からご指摘を受ける 2013/12/13修正完了)
sum({1,3,6}) = 10,
sum({1,3,8}) = 12,
sum({1,3,10}) = 14,
sum({1,3,11}) = 15,
sum({1,6,8}) = 15,
sum({1,6,10}) = 17,
sum({1,6,11}) = 18,
sum({1,8,10}) = 19,
sum({1,8,11}) = 20,
sum({1,10,11}) = 22,
sum({3,6,8}) = 17,
sum({3,6,10}) = 19,
sum({3,6,11}) = 20,
sum({3,8,10}) = 21,
sum({3,8,11}) = 22,
sum({3,10,11}) = 24,
sum({6,8,10}) = 24,
sum({6,8,11}) = 25,
sum({6,10,11}) = 27,
sum({8,10,11}) = 29.
これらの和は1つしか現れない場合もそうでない場合もある. 集合Aについて, U(A,k)で, Aのk要素の集合全体について和を取ったときに1回のみ現れる和の集合を表す. 上の例をとると, U(B,3) = {10,12,14,18,21,25,27,29}であり, sum(U(B,3)) = 156となる.
今, 100個の要素を持つ集合 S = {1^2, 2^2, ..., 100^2}を考える. Sの50要素の部分集合は100891344545564193334812497256個ある.
50要素の部分集合の和の中で1回のみ現れる和の集合の総和を求めよ. すなわち, sum(U(S,50))を求めよ.
解法
真面目に数えると計算量やメモリ使用量が多くなる問題です。
この問題はある数ｎをｍ種類の数を使って作れたとき
0,1,2,3通り以上の作り方があるという４種類の集計以外しないことをもって計算量とメモリ使用量を下げます。
0,1,2,3以上の集計にはビット演算を使い、組み合わせ数の作り方は動的計画法で行います。
50個で解説するのは大変なので、１０個の中から５個選ぶ場合で考えてみましょう。
10個の数字をa1,a2,,,,a10とその合計をLimitとします。
そしてある数ｎを少なくとも一通りか二通りで作れた場合を集計するために
- count1[Limit+1]
- count2[Limit+1]
の2種類の配列を用意し型は６４ビット整数型とします。
(128bit整数型が使えるならcount1とcount2を統合したほうが少し計算が速くなりますがここではわかりやすさを重視して２つに分けます)
例
図のcount1は
右１ビット目は０種類の数を使って少なくとも１通りの方法で12が作れたかどうかを現す（1なら作れた0なら作れてないで0種類の数を使って作れる数は0だけであるので絶対にビットは立たない）
右２ビットめは１種類の数を使って少なくとも１通りの方法で12が作れたら１となる。
右３ビット目は２種類の数を使って少なくとも１通りの方法で12が作れたら１となる。
、、、
右6ビット目は5種類の数を使って少なくとも１通りの方法で12が作れたら１となる。
であり図では６ビット目と３ビット目に1のフラグがたっているので。
２種類か５種類の数字を使って少なくとも一つ１２という数を作れたということを現します。
たとえば3+4+5＝12で12という数が作れたらcount1[12]=00,,,001000
と４ビット目（３種類の数で少なくとも一つ作れた）に１ビットフラグがたちます。
図のcount2は
右１ビット目は０種類の数を使って少なくとも２通りの方法で12が作れたかどうかを現す（1なら作れた0なら作れてないでN=0以外ではこのビットは立たない）
右２ビットめは１種類の数を使って少なくとも２通りの方法で12が作れたら１となる。
右３ビット目は２種類の数を使って少なくとも２通りの方法で12が作れたら１となる。
、、、
右6ビット目は5種類の数を使って少なくとも２通りの方法で12が作れたら１となる。
計算方法
count1,count2を使って計算を行います。
count1とcount2を全て0にし
count1[0]=1とします。
これは最右ビットの１を立てる。
0という数を0種類の数で作れたということを設定したことになります。
組み合わせを計算するのですが
計算手法を解説します。(もちろん解説が楽な１０個から５個選ぶ場合の解説です)
計算手順
a1が5でＬｉｍｉｔが62だったとします。
最初0に５を足したものだけを考えるので。
Pを0として以下の計算を実行します。
- 式A count2[P+5]|=(count1[P+5]&(count1[P]<<1));
- 式B count1[P+5]|=(count1[P]<<1);
- 式C count2[P+5]|=(count2[P]<<1)
- 式D count1[P+5]&=63;
- 式E count2[P+5]&=63;
(演算子の表記方法はＣ++準拠です)。
次の数字がa2=8などなら式の添え字を[P+8]としＰを5～0まで動かし上記と同じ計算を繰り返します。
次の数字がa3=7などなら式の添え字を[p+7]としＰを13(8+5)～0まで動かし上記と同じ計算を繰り返します。
あとはa10まで上記作業を繰り返します。
最後にp=0～Ｌｉｍｉｔまで動かしcount1[P]の６ビット目が１でcount2[P]の６ビット目が0となっている組み合わせのＰを足し合わせたら答えとなります。
Ａの計算です。
ある程度計算が進み5を足して7から１２を作る場合の例。
まずここでは２通り以上の方法で12を現せることが判明した場合を計算します。
次は式Ｂの計算です
次に少なくとも一通りの方法で１２を現せることが判明した場合を更新する方法です。
Ｂの計算は上図で終わりです。
ここで忘れてはいけないのはcount2[7]でｍ種類の数を使って２通り以上の方法で12を作れた場合これに５を足して12を作った場合です。
Ｃの計算を行います。
式ＤとＥは６種類以上の数で数Ｎを作れた場合というはみ出しを消去するための単なるビットマスクです。
100種類で５０個の場合も計算手順通り行えば同様に計算できます。
最終更新：2013年12月13日 11:41
