2.2 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f4361000cf542c50ff48 | 問題 201: 唯一の和を持つ部分集合 | 5 | 301841 | problem-201-subsets-with-a-unique-sum |
--description--
数の任意の集合 A について、A の要素の和を sum(A) とします。
集合 B = \\{1,3,6,8,10,11\\} を考えてみます。 B には 3 要素からなる部分集合が 20 個あり、それぞれの和は次のとおりです。
$$\begin{align} & 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 \end{align}$$
これらの和には、複数回現れるものと、1 回のみ現れるものがあります。 集合 A について、A の k 個の要素からなる部分集合のうち、その和が全体で 1 回だけ現れるような集合を $U(A,k) と表すことにします。上の例では、U(B,3) = \\{10,12,14,18,21,25,27,29\\} かつ sum(U(B,3)) = 156 です。
次に、100 個の要素からなる集合 S = \\{1^2, 2^2, \ldots , {100}^2\\} を考えます。 S には 50 個の要素からなる部分集合が 100\\,891\\,344\\,545\\,564\\,193\\,334\\,812\\,497\\,256\\; 個あります。
集合 S について、50 個の要素からなる部分集合の和のうち 1 回のみ現れる和である整数の総和、すなわち sum(U(S,50)) を求めなさい。
--hints--
uniqueSubsetsSum() は 115039000 を返す必要があります。
assert.strictEqual(uniqueSubsetsSum(), 115039000);
--seed--
--seed-contents--
function uniqueSubsetsSum() {
return true;
}
uniqueSubsetsSum();
--solutions--
// solution required