「プロジェクトオイラー解説問201」の編集履歴（バックアップ）一覧はこちら
プロジェクトオイラー解説問201 - (2013/12/09 (月) 08:25:35) の１つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
*Problem 201 「唯一の和を持つ部分集合」 †
----
問題
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))を求めよ.
----
只今図準備中。
真面目に数えると計算量やメモリ使用量が多くなる問題です。
この問題はある数ｎをｍ種類の数を使って作れたとき
0,1,2,3通り以上の作り方があるという４種類の集計以外しないことをもって計算量とメモリ使用量を下げます。
0123以上の集計にはビット演算を使い、組み合わせ数の作り方は動的計画法で行います。
50個で解説するのは大変なので、１０個の中から５個選ぶ場合で考えてみましょう。
10個の数字をa1,a2,,,,a10とその合計をLimitとします。
そしてある数ｎを少なくとも一種類で作れた場合を集計するために
-count1[Limit+1]
-count2[Limit+1]
の2種類の配列を用意し型は６４ビット整数型とします。
例
#ref(e201_1.gif)
図のcount1は
右１ビット目は０種類の数を使って少なくとも１通りの方法で12が作れたかどうかを現す（1なら作れた0なら作れてないで0種類の数を使って作れる数は0だけである）
右２ビットめは１種類の数を使って少なくとも１通りの方法で12が作れたら１となる。
右３ビット目は２種類の数を使って少なくとも１通りの方法で12が作れたら１となる。
、、、
であり図では６ビット目と３ビット目に1のフラグがたっているので。
２種類か５種類の数字を使って少なくとも一つ１２という数を作れたということを現します。
図のcount2は
右１ビット目は０種類の数を使って少なくとも２通りの方法で12が作れたかどうかを現す（1なら作れた0なら作れてないでN=0以外ではこのビットは立たない）
右２ビットめは１種類の数を使って少なくとも２通りの方法で12が作れたら１となる。
右３ビット目は２種類の数を使って少なくとも２通りの方法で12が作れたら１となる。
、、、
----
***計算方法
count1,count2を使って計算を行います。
count1とcount2を全て0にし
count1[0]=1とします。
これは最右ビットの１を立てる0という数を0種類の数で作れたということを計算したことになります。
ここで適当に
a1が5でＬｉｍｉｔが62だったとします。
Pを57(62-5)～0まで動かし。
count1[P+5]|=(count1[P]<<1);
count2[P+5]|=(count1[P+5]&(count1[P]<<1));
count2[P+5]|=(count2[P]<<1)
count1[P+5]&=63;
count2[P+5]&=63;
という計算を実行します。
次の数字がa2=8などなら
Pを54(62-8)～0まで動かし上記と同じ計算を繰り返し。
a10まで繰り返します。
この計算の意味については今から図で説明します。
*Problem 201 「唯一の和を持つ部分集合」 †
----
問題
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))を求めよ.
----
只今図準備中。
真面目に数えると計算量やメモリ使用量が多くなる問題です。
この問題はある数ｎをｍ種類の数を使って作れたとき
0,1,2,3通り以上の作り方があるという４種類の集計以外しないことをもって計算量とメモリ使用量を下げます。
0123以上の集計にはビット演算を使い、組み合わせ数の作り方は動的計画法で行います。
50個で解説するのは大変なので、１０個の中から５個選ぶ場合で考えてみましょう。
10個の数字をa1,a2,,,,a10とその合計をLimitとします。
そしてある数ｎを少なくとも一種類で作れた場合を集計するために
-count1[Limit+1]
-count2[Limit+1]
の2種類の配列を用意し型は６４ビット整数型とします。
例
#ref(e201_1.gif)
図のcount1は
右１ビット目は０種類の数を使って少なくとも１通りの方法で12が作れたかどうかを現す（1なら作れた0なら作れてないで0種類の数を使って作れる数は0だけであるので絶対にビットは立たない）
右２ビットめは１種類の数を使って少なくとも１通りの方法で12が作れたら１となる。
右３ビット目は２種類の数を使って少なくとも１通りの方法で12が作れたら１となる。
、、、
右6ビット目は２種類の数を使って少なくとも１通りの方法で12が作れたら１となる。
であり図では６ビット目と３ビット目に1のフラグがたっているので。
２種類か５種類の数字を使って少なくとも一つ１２という数を作れたということを現します。
図のcount2は
右１ビット目は０種類の数を使って少なくとも２通りの方法で12が作れたかどうかを現す（1なら作れた0なら作れてないでN=0以外ではこのビットは立たない）
右２ビットめは１種類の数を使って少なくとも２通りの方法で12が作れたら１となる。
右３ビット目は２種類の数を使って少なくとも２通りの方法で12が作れたら１となる。
、、、
右6ビット目は２種類の数を使って少なくとも２通りの方法で12が作れたら１となる。
----
***計算方法
count1,count2を使って計算を行います。
count1とcount2を全て0にし
count1[0]=1とします。
これは最右ビットの１を立てる。
0という数を0種類の数で作れたということを設定したことになります。
ここで適当に
a1が5でＬｉｍｉｔが62だったとします。
Pを57(62-5)～0まで動かし。
-A count1[P+5]|=(count1[P]<<1);
-B count2[P+5]|=(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を54(62-8)～0まで動かし上記と同じ計算を繰り返し。
a10まで上記作業を繰り返し。
最後にp=0～Ｌｉｍｉｔまで動かしcount1[P]の６ビット目が１でcount2[P]の６ビット目が0となっている組み合わせの個数を数えたら答えとなります。
この計算の意味については今から図で説明します。
#ref(e201_1.gif)
