C - 無駄なものが嫌いな人 (arc017_3) 半分全列挙

Quiz

AC

解き方

  • 前半後半で半分に分ける(N=16ずつ)
  • 前半のみで、各荷物を使うかどうか0/1で全パターン試す。216 = 65536
  • 後半も同様
  • 解説では二分探索と書かれていたがmapでも解けた

半分全列挙

  • 半分毎に処理すれば間に合う時に使う
    • O(2N)では間に合わないが、O(2N/2)なら間に合う(し、メモリにも乗る)
  • いい感じに分割するという点では平方分割と似ている?

code

// map[weight_wum] = count を返す
map<ll,ll> f(VI A){
  ll N = A.size();
  map<ll,ll> mp;
  // bit全探索
  rep(f,1<<N){
    ll sum=0;
    rep(i,N){
      if(f>>i&1){
        // i番目を使う
        sum += A[i];
      }
    }
    mp[sum]++;
  }
  return mp;
}

int main(){
    ll N,X;
    cin>>N>>X;

    VI A, B; // 前半後半に分ける

    rep(i,N){
      ll w;cin>>w;
      if(i<N/2){
        A.push_back(w);
      }else{
        B.push_back(w);
      }
    }

    auto mp0 = f(A);
    auto mp1 = f(B);

    ll ans=0;
    for(auto pa : mp0){
      ll v = pa.first;
      ll cnt = pa.second;

      ll rest = X-v;
      if(rest<0)continue;
      if(mp1.count(rest)==0)continue;
      ans += cnt * mp1[rest];
    }

    p(ans);
    
    return 0;
}