本番一瞬迷ったけど持ち直した。
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); }
まとめ
半分全列挙が思い浮かべば答えはすぐ。