PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 105 / 特殊和集合:検査

大きさ n の集合 A の要素の和を S(A) で表す。空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば,A を特殊和集合と呼ぼう。

  1. S(B)≠S(C); つまり,部分集合の和はすべて異なる
  2. 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 を用いて特殊和集合 A1, A2, ... , Ak をすべて特定し,
S(A1) + S(A2) + ... + S(Ak) を求めよ。


Problem 105 - Project Euler


素朴に考えて解きました。下手にサブリストを作ると Map や Apply の作用の仕方がわからなくなってしまいそうなので,sets.txt の要素を1つずつ取り出してチェックしています。

まず,部分集合を要素数 i でグループ分けして,和の最大値 max(i) と最小値 min(i) を求めます。

条件1のチェックは簡単で, DuplicateFreeQ するだけ。

条件2は max(i) < min(i+1) で調べました。

特に工夫するまでもなく1.4秒で終わって,ホッとしました。