TopCoder SRM 622 Div2 Hard Subsets

なんとなくDiv2 Hardっぽい問題。
http://community.topcoder.com/stat?c=problem_statement&pm=10554

問題

N要素からなる自然数の集合numbers[i]が与えられる。
numbers[i]の空でない部分集合のうち、要素の総和が要素の積より大きくなるものの数を答えよ。

なお、numbers[i]中同じ数字が複数ある場合、それらは区別されない。

解法

ネットではDFSの解法も見かけたけど、こちらはDPで。

途中まで選んだ部分集合の要素の総和をA,積をBとする。
Bが２以上の場合、この部分集合に2以上の値を追加するとAよりBの方が増加分が大きい。
逆にAの方がBより増加分が大きいのは部分集合に1を追加する場合である。

よって、numbers[i]に含まれる小さい数から順にDPしていけばよい。
組み合わせ数としてDP[A][B]を状態にとると、ある数xをy個(y=1～number[x])追加してもA+x*y > B*x^yが維持できるなら、その組み合わせを追加していく。

xが大きくなるとA+x*y > B*x^yとなるBはAに対しだいぶ小さくなるため、最初はxごとにO(AB)程度ループするがだんだんO(A)に近づいていく。

また、Aの上限は1000を少し上回る程度までループすればよい。
A > Bを維持したままAが大きくなるのは、部分集合に大量の1と幾つかの2以上の数を追加する場合であり、トータルでAはあまり大きくならない。

ll dpdp[2002][2002];
int num[1001];

class Subsets {
	public:
	int findSubset(vector <int> numbers) {
		int i,j,k,g,x,y;
		
		ZERO(num);
		ZERO(dpdp);
		FOR(i,numbers.size()) num[numbers[i]]++;
		
		FOR(i,num[1]+1) dpdp[i][1]=1;
		
		for(i=2;i<=1000;i++) if(num[i]) {
			for(x=1200;x>=0;x--) {
				g=1;
				for(j=1;j<=num[i];j++) {
					k=i*j;
					g*=i;
					if(x+k>1900 || g>1900) break;
					FOR(y,1201) {
						if(y*g>x+k) break;
						dpdp[x+k][y*g]+=dpdp[x][y];
					}
				}
			}
		}
		ll ret=0;
		FOR(x,2001) FOR(y,x) ret+=dpdp[x][y];
		return ret;
	}
}

まとめ

最初1がたくさんある場合にTLEするコードを書いてしまった。