Problem 105 のバックアップ(No.1)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 105 へ行く。
  • 1 (2015-09-16 (水) 09:52:06)

Problem 105 「特殊和集合:検査」 †

大きさ 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 集合である), 特殊和集合 A&sub{1};, A&sub{2};, ... , A&sub{k}; をすべて特定し, S(A&sub{1};) + S(A&sub{2};) + ... + S(A&sub{k};) を求めよ.

注意: この問題は Problem 103 と 106 に関連している.