SRM407: PointsGame

(問題概要)
平面上の点(12個以下)を自分が赤、相手が青で自分から交互に塗っていく。
最後に色の違う点の全対に対して、距離の和が得点になる。
相手は得点を最小にするように最適に動く。
最大何点得られるか。

(解法)
点の数が少ないので、bitDPすれば良い。
ただし愚直にやるとMLE食らったので、mapを使った。

#include <map>
#include <cstdio>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>
#include <cmath>

using namespace std;

class PointsGame {
public:
  double gameValue(vector <int> pointsX, vector <int> pointsY);
};

map<int, double> memo[1 << 12];
vector<int> x;
vector<int> y;
int n;

double dist(int i, int j){
  const double d1 = x[i] - x[j];
  const double d2 = y[i] - y[j];
  return sqrt(d1 * d1 + d2 * d2);
}

double solve(int f1, int f2){
  if(memo[f1].count(f2)) return memo[f1][f2];
  if((f1 | f2) == (1 << n) - 1){
    double p = 0;
    REP(i,n) if(f1 & (1 << i))
      REP(j,n) if(f2 & (1 << j))
	p += dist(i, j);
    return memo[f1][f2] = p;
  }

  const int k1 = __builtin_popcount(f1);
  const int k2 = __builtin_popcount(f2);

  if(k1 == k2){
    double mx = 0.0;
    REP(i,n) if( ((f1 | f2) & (1 << i)) == 0 ){
      mx = max(mx, solve(f1 | (1 << i), f2));
    }
    return memo[f1][f2] = mx;
  }else{
    double mn = 1e10;
    REP(i,n) if( ((f1 | f2) & (1 << i)) == 0 ){
      mn = min(mn, solve(f1, f2 | (1 << i)));
    }
    return memo[f1][f2] = mn;
  }
}

double PointsGame::gameValue(vector <int> pointsX, vector <int> pointsY){
  REP(i,1<<12) memo[i].clear();
  x = pointsX; y = pointsY;
  n = pointsX.size();
  return solve(0, 0);
}