ビットマスクでの全探索の処理時間

例

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
#include<sstream>
#include<queue>
#include<climits>
#include<numeric>
#include<functional>
#include<ctime>
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define fi(i,j,k) fill(i[0],i[0]+j*j,k)
#define INF 1<<25
static const double eps=1e-10;
typedef long long ll;
typedef std::pair<int,int> P;
using namespace std;

// Range:n 1 < n 

//ans = 19 {1(a),3(b),5(b),10(a)}

/*
                    i1 ------> i2 ------> i3 ------> i4
                    (a=1,b=2)  (a=4,b=3)  (a=6,b=5)  (a=10,b=11)
  optimum answer        1          3          5         10
  
 */

int main(void){
   clock_t start,end;
   start = clock();
   int n=4;
   int a[]={1,4,6,10};
   int b[]={2,3,5,11};
   int Min=INF;
   for(int i=0;i<(1<<n);i++){
      int sum=0;
      for(int j=0;j<n;j++){
         if((i & (1<<j)) != 0){
            sum+=a[j];
         }
         else{
            sum+=b[j];
         }
      }
      if(Min > sum) Min = sum;
   }
   cout << Min << endl;
   end = clock();
   cout <<"processing time = "<< (double)((end-start)/CLOCKS_PER_SEC) << endl;
   return 0;
}

実験用プログラム

int main(void){
   clock_t start,end;
   start = clock();
   int n=?; 
   vector<int> a(n);
   vector<int> b(n);
   rep(i,n){
      a[i] = i;
      b[i] = i;
   }
   int Min=INF;
   for(int i=0;i<(1<<n);i++){
      int sum=0;
      for(int j=0;j<n;j++){
         if((i & (1<<j)) != 0){
            sum+=a[j];
         }
         else{
            sum+=b[j];
         }
      }
      if(Min > sum) Min = sum;
   }
   cout << Min << endl;
   end = clock();
   cout <<"processing time = "<< (double)((end-start)/CLOCKS_PER_SEC) << endl;
   return 0;
}

windows7 ultimate 64bitで計測
この結果はあくまで目安なので。

n = 15 ans = 105 time = 0;
n = 20 ans = 190 time = 0;
n = 21 ans = 210 time = 0;
n = 22 ans = 231 time = 0;

ここから一秒台に入って来ました

n = 23 ans = 253 time = 1;
n = 24 ans = 276 time = 3;
n = 25 ans = 300 time = 6;
n = 26 ans = 325 time = 14;

結論
競技で使うときは大体 n = 20 が限界だと思う。