torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, SRM 622, Division 2, Level 3 : Subsets

問題概要

 正整数の(多重)集合 S が与えられる。この集合の部分集合 T であって、\sum T > \prod T であるものの数を求めよ。
 |S| \leq 1000 であり、任意の a ∈ S について 1 \leq a \leq 1000 である。
 また、答えは 32 bit 符号付き整数で表現できることが保証される。

解法

 S の要素が互いに相異なる場合、選び方の総数は最大で 2^{1000} となるはずですが、Notes では答えは 2^{31} 未満であると主張されています。まずはこのことについて考えます。総和が最大値をとるのは、|T| = 1000 かつ全ての要素が最大値 1000 をとるときなので、1000 \times 1000 = 10^6 です。一方、題意より、総乗は総和未満でなければなりません。乗法単位元である 1 を乗じる場合の総乗の挙動は自明なのでこれを除外して考えると、条件を満たす部分集合の要素数は高々 \log_2 10^6 です。というのも、条件を満たす部分集合の要素数が最大となるのは全ての要素が 2 のときですが、(指数を整数に限定すれば)2 を \lceil \log_2 10^6 \rceil 乗すると、部分集合の総和と総乗に関する条件を満たせなくなってしまうことによります。\lceil \log_2 10^6 \rceil = 20 なので、条件を満たす部分集合の要素数は 20 未満となります。相反する仮定を置いて最大・最小を考えたので実際はもっと少ないと思われますが、上界の見積もりということでよしとしておきます。
 さて、先頭の要素から順番に部分集合に加える/加えないを決めていく DFS を考えると、部分集合が確定するまでの分岐の回数は高々 19 回です。従って、次の二種類の枝刈り

  • 総和が総乗以下になるのが確定したら、条件を満たす部分集合を作れないので 0 を return
  • これ以上何かを部分集合に加えると総和が総乗以下になることが確定したら、以降選択肢が無いので 1 を return

を加えると、探索木に於ける葉ノードの数は 2^{19} 個程度に抑えられます。どちらの条件判定も、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;
	}
};