※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

Problem 201 「唯一の和を持つ部分集合」 †

変更履歴
(*2013/12/10 らすかるさんというかたから計算方法に記述ミスがあると指摘を受け修正、まだ解説サイトを始めたばかりで不慣れなためにこういうミスは減らさねばとよい自戒となる、12月11日図の修正完了)
(*2013/12/13 図の説明のBitが1桁ずれていること一部の解説がわかりにくいことをaerile_reさんという方からご指摘を受ける 2013/12/13修正完了)


問題
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20201
数の集合Aについて, sum(A)でAの要素の和を表す. 集合B = {1,3,6,8,10,11}を考えよう. Bの3要素の部分集合は20個あり, それぞれ和は以下になる.

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))を求めよ.

解法

真面目に数えると計算量やメモリ使用量が多くなる問題です。
この問題はある数nをm種類の数を使って作れたとき
0,1,2,3通り以上の作り方があるという4種類の集計以外しないことをもって計算量とメモリ使用量を下げます。
0,1,2,3以上の集計にはビット演算を使い、組み合わせ数の作り方は動的計画法で行います。


50個で解説するのは大変なので、10個の中から5個選ぶ場合で考えてみましょう。
10個の数字をa1,a2,,,,a10とその合計をLimitとします。

そしてある数nを少なくとも一通りか二通りで作れた場合を集計するために
  • count1[Limit+1]
  • count2[Limit+1]
の2種類の配列を用意し型は64ビット整数型とします。
(128bit整数型が使えるならcount1とcount2を統合したほうが少し計算が速くなりますがここではわかりやすさを重視して2つに分けます)

図のcount1は
右1ビット目は0種類の数を使って少なくとも1通りの方法で12が作れたかどうかを現す(1なら作れた0なら作れてないで0種類の数を使って作れる数は0だけであるので絶対にビットは立たない)
右2ビットめは1種類の数を使って少なくとも1通りの方法で12が作れたら1となる。
右3ビット目は2種類の数を使って少なくとも1通りの方法で12が作れたら1となる。
、、、
右6ビット目は5種類の数を使って少なくとも1通りの方法で12が作れたら1となる。

であり図では6ビット目と3ビット目に1のフラグがたっているので。
2種類か5種類の数字を使って少なくとも一つ12という数を作れたということを現します。


たとえば3+4+5=12で12という数が作れたらcount1[12]=00,,,001000
と4ビット目(3種類の数で少なくとも一つ作れた)に1ビットフラグがたちます。


図のcount2は
右1ビット目は0種類の数を使って少なくとも2通りの方法で12が作れたかどうかを現す(1なら作れた0なら作れてないでN=0以外ではこのビットは立たない)
右2ビットめは1種類の数を使って少なくとも2通りの方法で12が作れたら1となる。
右3ビット目は2種類の数を使って少なくとも2通りの方法で12が作れたら1となる。
、、、
右6ビット目は5種類の数を使って少なくとも2通りの方法で12が作れたら1となる。


計算方法

count1,count2を使って計算を行います。
count1とcount2を全て0にし
count1[0]=1とします。
これは最右ビットの1を立てる。
0という数を0種類の数で作れたということを設定したことになります。


組み合わせを計算するのですが
計算手法を解説します。(もちろん解説が楽な10個から5個選ぶ場合の解説です)

計算手順

a1が5でLimitが62だったとします。
最初0に5を足したものだけを考えるので。
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;

(演算子の表記方法はC++準拠です)。
次の数字がa2=8などなら式の添え字を[P+8]としPを5~0まで動かし上記と同じ計算を繰り返します。
次の数字がa3=7などなら式の添え字を[p+7]としPを13(8+5)~0まで動かし上記と同じ計算を繰り返します。
あとはa10まで上記作業を繰り返します。
最後にp=0~Limitまで動かしcount1[P]の6ビット目が1でcount2[P]の6ビット目が0となっている組み合わせのPを足し合わせたら答えとなります。

Aの計算です。

ある程度計算が進み5を足して7から12を作る場合の例。
まずここでは2通り以上の方法で12を現せることが判明した場合を計算します。

次は式Bの計算です

次に少なくとも一通りの方法で12を現せることが判明した場合を更新する方法です。
Bの計算は上図で終わりです。

ここで忘れてはいけないのはcount2[7]でm種類の数を使って2通り以上の方法で12を作れた場合これに5を足して12を作った場合です。
Cの計算を行います。

式DとEは6種類以上の数で数Nを作れた場合というはみ出しを消去するための単なるビットマスクです。


100種類で50個の場合も計算手順通り行えば同様に計算できます。