TopCoder SRM 798 : Div1 Easy Div2 Hard SuperSubset

またMedium凡ミスした…。
https://community.topcoder.com/stat?c=problem_statement&pm=16218&rd=18491

問題

N要素の整数列Aと正整数Yがある。
0～(N-1)の集合Sに対し、Sの重さw(S)とは、Sの部分集合S'のうち、x∈S'におけるA[x]の総和がYとなるものの個数である。

Sとして0～(N-1)の部分集合全通りを考えたとき、w(S)の総和を答えよ。

解法

S及びw(S)を考えるとき、0～(N-1)のそれぞれについて、下記3通りが考えられる。

• Sに含まない
• Sに含まれるが、S'に含まれる
• SにもS'にも含まれる

あとはS'に含む要素xにおけるA[x]の総和に対し、それを満たす組み合わせの数をDPで数え上げよう。
ちょっと重いがO(NY)で解くことができる。

ll dp[10000];
const int mo=1000000007;
class SuperSubset {
	public:
	int solve(vector <int> A, int Y) {
		ZERO(dp);
		dp[Y]=1;
		FORR(a,A) {
			int i;
			FOR(i,Y+1) {
				dp[i]+=dp[i];
				if(i+a<=Y) dp[i]+=dp[i+a];
				dp[i]%=mo;
			}
		}
		return dp[0];
	}
}

まとめ

本番しょうもないミスでタイムロスした。まぁ1Chalのお陰で実質影響なかったんだけど。