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); }