超初心者が競プロに挑む

初心者からの競プロ練習記録

ARC017C解いてみた

久しぶりに自力で解ける問題見つけました。蟻本の類題ですね!
このように集合を半分に分けて列挙して答えを求めることを半分全列挙と呼ぶらしいです。

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int BucketA[(1<<16) + 10];
int BucketB[(1<<16) + 10];

int main(){
  int N,X;
  int w[32];

  memset(BucketA,0,sizeof(BucketA));
  memset(BucketB,0,sizeof(BucketB));

  scanf("%d%d", &N, &X);
  for(int i=0;i<N;++i) {
    scanf("%d", &w[i]);
  }
  int sA,sB;
  if(N>=16) {
    sA=16;sB=N-sA;
  } else {
    sA=N;sB=0;
  }
  for(int i=0;i< (1<<sA); ++i){
    for(int j=0;j<sA;++j) {
      if(((i>>j) & 1) == 1) {
        BucketA[i] += w[j];
      }
    }
  }
  for(int i=0;i< (1<<sB); ++i){
    for(int j=0;j<sB;++j) {
      if(((i>>j) & 1) == 1) {
        BucketB[i] += w[j + sA];
      }
    }
  }

  sort(BucketA, BucketA+(1<<sA));
  sort(BucketB, BucketB+(1<<sB));

  int ans = 0;

  for(int i=0;i<(1<<sA);++i) {
    ans+=upper_bound(BucketB, BucketB+(1<<sB), X-BucketA[i])
      - lower_bound(BucketB, BucketB+(1<<sB), X-BucketA[i]);
  }

  printf("%d\n", ans);

  return 0;
}