AtCoder ARC #017 : C - 無駄なものが嫌いな人

本番一瞬迷ったけど持ち直した。
http://arc017.contest.atcoder.jp/tasks/arc017_3

問題

N個の荷物があり、それぞれの大きさはw[i]である。
これらの荷物のうち幾つかを選び、大きさの総和をぴったりXにしたい。
そのような荷物の選び方は何通りあるか。

解法

N<=32のため、単純に選ぶ・選ばないを2^32通り行うとTLEする。
また、w[i]やXの範囲は10^9と大きく、大きさを用いたDPをしてもTLEする。

注目すべきは、条件が「総和がX以下」でなく「総和がぴったりX」であることである。
ここで蟻本の半分全列挙が適用できる。

まず、前半16個に対して2^16通り全列挙して、個々の大きさの和の組みわせ数を列挙する。
同様に後半16個に対しても全列挙する。

前半16個の総和がPの時の組み合わせ数をF(P)とし、後半16個の総和がQの時の組み合わせ数をG(Q)とすれば、各Pに対しF(P)*G(X-P)の総和を取ったものが答え。

int N;
ll X;
ll W[33];
map<ll,ll> MM[2];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>X;
	FOR(i,N) cin>>W[i];
	
	int mask;
	FOR(mask,1<<16) {
		ll tot=0;
		FOR(i,16) {
			if(mask&(1<<i)) {
				if(i>=N) {
					tot=-1;
					break;
				}
				tot+=W[i];
			}
		}
		if(tot>=0) MM[0][tot]++;
		tot=0;
		FOR(i,16) {
			if(mask&(1<<i)) {
				if(i+16>=N) {
					tot=-1;
					break;
				}
				tot+=W[i+16];
			}
		}
		if(tot>=0) MM[1][tot]++;
	}
	
	ll ret=0;
	ITR(it,MM[0]) ret += it->second * MM[1][X-it->first];
	_P("%lld\n",ret);
}

まとめ

半分全列挙が思い浮かべば答えはすぐ。