問題概要
正整数の(多重)集合 S が与えられる。この集合の部分集合 T であって、 であるものの数を求めよ。
であり、任意の a ∈ S について である。
また、答えは 32 bit 符号付き整数で表現できることが保証される。
解法
S の要素が互いに相異なる場合、選び方の総数は最大で となるはずですが、Notes では答えは 未満であると主張されています。まずはこのことについて考えます。総和が最大値をとるのは、|T| = 1000 かつ全ての要素が最大値 1000 をとるときなので、 です。一方、題意より、総乗は総和未満でなければなりません。乗法単位元である 1 を乗じる場合の総乗の挙動は自明なのでこれを除外して考えると、条件を満たす部分集合の要素数は高々 です。というのも、条件を満たす部分集合の要素数が最大となるのは全ての要素が 2 のときですが、(指数を整数に限定すれば)2 を 乗すると、部分集合の総和と総乗に関する条件を満たせなくなってしまうことによります。 なので、条件を満たす部分集合の要素数は 20 未満となります。相反する仮定を置いて最大・最小を考えたので実際はもっと少ないと思われますが、上界の見積もりということでよしとしておきます。
さて、先頭の要素から順番に部分集合に加える/加えないを決めていく DFS を考えると、部分集合が確定するまでの分岐の回数は高々 19 回です。従って、次の二種類の枝刈り
- 総和が総乗以下になるのが確定したら、条件を満たす部分集合を作れないので 0 を return
- これ以上何かを部分集合に加えると総和が総乗以下になることが確定したら、以降選択肢が無いので 1 を return
を加えると、探索木に於ける葉ノードの数は 個程度に抑えられます。どちらの条件判定も、S の要素を昇順に処理することで上手く判定できます。
また、同じ値は区別しないので、同値となる要素をまとめて処理する必要があります。
コード
using VI = vector<int>; #define FOR( e, c ) for ( auto &e : c ) class Subsets { public: VI nums; int findSubset( vector <int> numbers ) { nums = VI( 1001 ); FOR( a, numbers ) { nums[a]++; } return dfs( 0, 0, 0, 1 ); } int dfs( const int num, const int p, const int sum, const int prod ) { if ( 1000 < num ) { return sum > prod; } if ( 1 < prod && sum <= prod ) { return 0; } if ( 1 < prod && sum + num <= prod * num ) { return 1; } int res = 0; if ( p < nums[ num ] ) { res += dfs( num, p + 1, sum + num, prod * num ); } res += dfs( num + 1, 0, sum, prod ); return res; } };