半分全列挙

その名の通り、半分ずつ全列挙するアルゴリズムです。

早速、どんな問題で使えるかです。

問題

N個の商品があります。
i個目の商品の値段はAi円です。
何個かの商品を買うとき、ちょうどぴったり値段の合計がX円になる組み合わせはありますか？
もしあるなら買う商品の番号も出力してください。

制約
1<=n<=40
1<=A[i]<=1e9

実行時間は2sec以内

みたいな問題とか。

半分全列挙を知らなければ、パット見、bit全探索でときたいな…となるかもしれません。
しかし、単純なbit全探索だと最大で計算量が2^40となってしまい、間に合いません。

このときに半分全列挙で解くことができます。
半分全列挙はbit全探索と対して変わりません。

…というのも、例えば商品の個数が40個あったとき、一度に全探索しようとすると計算量が2^40になってしまいますが、半分ずつ、20個ずつ全探索すれば計算量が2^20*2となり、実行時間に間に合わせることができます。

Bit全探索ができるのなら、半分全列挙の実装もそこまで難しくはないと思います。

AOJにちょうどいい問題があります
onlinejudge.u-aizu.ac.jp

使うコインの枚数が決められているのが少々やっかいですが意外と少しコードを足すだけで大丈夫です。
半分全列挙を使わないで単純な全探索で通る（例えばN<=20）の場合は普通のBit全探索で通したほうが実装が楽になります。

#include<iostream>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
int main()
{
  int n,k;
  long long l,r;
  cin >> n >> k >> l >> r;
  vector<long long>a(n);
  for(int i=0;i<n;i++)cin >> a[i];
  if(n<=20){
    long long ans=0;
    for(int tmp=0;tmp<(1<<n);tmp++){
      bitset<20>s(tmp);
      int cnt=0;
      for(int i=0;i<n;i++)if(s[i])cnt++;
      if(cnt!=k)continue;
      long long count=0;
      for(int i=0;i<n;i++)if(s[i])count+=a[i];
      if(l<=count && count<=r)ans++;
    }
    cout << ans << endl;
    return 0;
  }
  vector<vector<long long>>num(21);
  for(int tmp=0;tmp<(1<<20);tmp++){
    bitset<20>s(tmp);
    int cnt=0;
    long long count=0;
    for(int i=0;i<n;i++)if(s[i])cnt++;
    for(int i=0;i<20;i++)if(s[i])count+=a[i];
    num[cnt].emplace_back(count);
  }
  for(int i=0;i<21;i++)sort(num[i].begin(),num[i].end());
  long long ans=0;
  for(int tmp=0;tmp<(1<<(n-20));tmp++){
    bitset<20>s(tmp);
    int cnt=0;
    long long count=0;
    for(int i=0;i<(n-20);i++)if(s[i])cnt++;
    if(cnt>k || k-cnt>20 || num[k-cnt].size()==0)continue;
    for(int i=0;i<(n-20);i++)if(s[i])count+=a[i+20];
    int left=-1,right=num[k-cnt].size(),mokuteki;
    while(left+1!=right){
      mokuteki=(left+right)/2;
      if(num[k-cnt][mokuteki]+count<l)left=mokuteki;
      else right=mokuteki;
    }
    int hako=right;
    left=-1,right=num[k-cnt].size();
    while(left+1!=right){
      mokuteki=(left+right)/2;
      if(num[k-cnt][mokuteki]+count>r)right=mokuteki;
      else left=mokuteki;
    }
    ans+=(right-hako);
  }
  cout << ans << endl;
}

提出結果
onlinejudge.u-aizu.ac.jp