日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。
問１０５「特殊和集合:検査」
大きさ n の集合 A の要素の和を S(A) で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば, A を特殊和集合と呼ぼう.
i. S(B)≠S(C); つまり, 部分集合の和が等しくてはならない.
ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.
たとえば, {81, 88, 75, 42, 87, 84, 86, 65} は,
65 + 87 + 88 = 75 + 81 + 84 であるため特殊和集合ではないが,
{157, 150, 164, 119, 79, 159, 161, 139, 158} は
すべての可能な部分集合の対の組み合わせについて両方のルールを満たしており, また S(A) = 1286 である.
7個 から 12個 の要素を含む 100 個の集合が記された 4K のテキストファイル sets.txt (右クリックして "名前をつけてリンク先を保存") を用いて (上の二例はファイルの最初の 2 集合である), 特殊和集合 A1, A2, ... , Ak をすべて特定し, S(A1) + S(A2) + ... + S(Ak) を求めよ.
注意: この問題は Problem 103 と 106 に関連している.
注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。
私の回答例は以下の通りです。
def chk1(L):
import itertools
M = []
for i in xrange(len(L)):
for j in itertools.combinations(L, i+1):
s = sum(j)
if s in M: return False
M.append(s)
return True
def chk2(L):
a, b = (len(L)+1)//2, len(L)//2+1
return sum(L[:a])>sum(L[b:])
def f(fn):
c, s = 0, 0
p = open(fn)
for t in p.readlines():
L = sorted([int(u) for u in t.split(",")])
if chk1(L) and chk2(L): s += sum(L); c += 1
p.close()
p = None
return s, c
t = os.path.join(os.path.dirname(__file__), "p105_sets.txt")
s, c = f(t)
print "sum :", s
print "count:", c
問題文にあるとおり、問１０３の関連問題です。
特殊和集合のチェックは既に問１０３でやっているので、そのまま流用しました。
１．関数chk1(L)
・リストLが最適特殊和集合の以下の条件、
i. S(B) ≠ S(C); つまり, 部分集合の和が等しくてはならない.
を満たしていればTrue、満たしていなければFalseを返します。
・詳細は問１０３を参照。
２．関数chk2(L)
・リストLが最適特殊和集合の以下の条件、
ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.
を満たしていればTrue、満たしていなければFalseを返します。
・詳細は問１０３を参照。
３．関数f(fn)
・入力ファイルのフルパスを受け取り、特殊和集合の合計値と個数を返します。
・入力ファイルを１行ずつ読み込み、カンマで分けて数値型の要素にして昇順に並べたリストLについて、特殊和集合の条件２つが成り立てば、変数cにためていきます。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
sum : 73702
count: 28
