K4PC : E - はじめての動的計画法(Easy Dynamic Programming)

面白い逆問題でした。本番解けなかったけど。
http://k4pc.contest.atcoder.jp/tasks/k4pc_e

問題

以下の典型DP問題を考える。

N個の荷物があり、それぞれの重さはA[i]である。
荷物の重さの合計がW以下となる荷物の部分集合の選び方は何通りあるか。
なお、1≦N≦1000、1≦W≦1000、1≦A[i]≦1000である。

Xが与えられるとする。
上記典型問題の答えがXとなるようなN,W,A[i]の例を答えよ。

解法

Wが十分大きいとき、A[i]==1の荷物がa個あると、2^a通りの選び方ができる。
この事実より、まず2^a ≦ X ＜ 2^(a+1)となるaを求め、a個A[i]==1である荷物を追加する。

この状態ではまあと(X - 2^a)通り分をどうにかしなければならない。
ここで、W=1000とし、重さ(1000-b)の荷物を１個追加したとする。
すると、重さ1のa個の荷物のうち、b個までは選択可能なので、そのような重さ(1000-b)の荷物を１個追加するごとに、通りの選び方を追加できる。

後は同様に、残りの組み合わせ数が0になるまで、重さ(1000-b)の荷物を追加していけば良い。
以下のコードは先にCombinationの累積和を計算している。

ll X;
ll C[1005][1005],S[1005][1005];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X;
	if(X==1) return _P("1 1\n5\n");
	
	FOR(i,100) C[i][0]=S[i][0]=S[0][i]=1;
	for(i=1;i<=100;i++) {
		for(x=1;x<=100;x++) {
			C[i][x]=min(1LL<<60,C[i-1][x]+C[i-1][x-1]);
			S[i][x]=min(1LL<<60,S[i][x-1]+C[i][x]);
		}
	}
	x=0;
	vector<int> V;
	while(1LL<<(x+1)<=X) x++, V.push_back(1);
	X -= 1LL<<x;
	
	for(y=x;y>=0;y--) {
		while(X>=S[x][y]) {
			V.push_back(1000-y);
			X-=S[x][y];
		}
	}
	
	_P("%d %d\n",V.size(),1000);
	ITR(it,V) _P("%d\n",*it);
}

まとめ

この方法は思いつかなかった。