Codeforces #360 Div1 C. The Values You Can Make

また問題読み間違える…。
http://codeforces.com/contest/687/problem/C

問題

N枚のコインがあり、それぞれの金額はC[i]である。
N枚のうち合計金額がKとなるように一部を選んだ時、さらにそのサブセットとして構成可能な金額を列挙せよ。

解法

以下の状態を考える。
F(i,a,b) := 先頭i枚のうち何枚か選んだ合計金額がaで、さらにそのサブセットとして金額bが構築可能か否か

以下の３重ループのDPを解くだけ。
F(i,a,b) := F(i-1,a,b) | F(i-1,a-C[i],b-C[i]) | F(i-1,a-C[i],b)
最終的にF(N,K,j)が1となるjを列挙すればよい。

以下のコードはbitsetで高速化している。

int N,K;
bitset<606> from[505];
bitset<606> to[505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	from[0][0]=1;
	FOR(i,N) {
		cin>>x;
		
		for(j=0;j<=K;j++) to[j] = from[j];
		for(j=0;j+x<=K;j++) {
			to[j+x] |= from[j];
			to[j+x] |= from[j]<<x;
		}
		swap(from,to);
	}
	vector<int> V;
	FOR(i,600) if(from[K][i]) V.push_back(i);
	_P("%d\n",V.size());
	FOR(i,V.size()) _P("%d%s",V[i],(i==V.size()-1)?"\n":" ");
}

まとめ

最初「金額K分コインを取り除いて、残りで構成できる金額」と勘違いした。