Project Euler 201

プロジェクトオイラー
http://projecteuler.net/index.php

Q201.
S = {12, 22, ... , 1002}という集合を考える。この部分集合で要素数が50のものの和を全て列挙したとき、重複しない和の集合をU(S,50)とする。この集合の要素の和を求めよ。

素数1の部分集合から考えた。和がダブったら、Uに同じ大きさの負の整数も入れておいて判別した。あとで和を取るとき、正のほうとキャンセルして、そのまま計算することができる。



def add(s, m):
if m in s:
s.add(-m)
else:
s.add(m)

def add2(s, m):
s.add(m)
s.add(-m)

N = 100
M = N / 2
a = [ set() for k in range(M + 1) ]
a[0].add(0)
for n in range(1, N + 1):
n2 = n * n

if n <= M:
start = n
end = 1
else:
start = M
end = n - M
for k in range(start, end - 1, -1):
for e in a[k-1]:
if e >= 0:
if e == 0 or -e not in a[k-1]:
add(a[k], e + n * n)
else:
add2(a[k], e + n * n)

print sum(a[M])