Codeforces #363 Div1 D. Limak and Shooting Points

計算量真面目に見なかったけどよく通ったなこれ。
http://codeforces.com/contest/698/problem/D

問題

２次元座標上で、K個の狙撃ポイントとN個の対象がある。
K個の狙撃ポイントから任意の順で１回ずつ、任意の方向に矢を放つ。
矢を放った先に対象がいた場合、狙撃ポイントに最も近いものにぶつかり、矢と狙撃ポイントは消滅する。

最適な順・方向で矢を放つとき、N個の対象のうち消滅させられる対象数を求めよ。

解法

まず各狙撃ポイントxに対し、各対象yの位置を偏角で分類し、各対象を消滅させるには手前あるどの頂点群を先に消滅させなければいけないかを求めよう。
この頂点の集合をf(x,y)とする。

あとは以下の状態を考える。
dp(mask, targets, shot) := maskが示す狙撃ポイントから、targetsに示す対象群を全滅させられるか否か。なおshotに示す対象群は消滅済み。
求めたいのは、各対象iに対しdp((1<

int K,N;
ll KX[10],KY[10];
ll PX[1111],PY[1111];
map<pair<int,int>,vector<pair<ll,int>>> M[8];
pair<int,int> key[1010][8];
int id[1010][8];


int can(int mask,vector<int> P, set<int> H) {
	if(__builtin_popcount(mask)<P.size()) return 0;
	if(P.empty()) return 1;
	int i,j,k;
	FOR(i,K) if(mask&(1<<i)) {
		FOR(j,P.size()) {
			int p=P[j];
			auto P2=P;
			P2.erase(P2.begin()+j);
			FOR(k,id[p][i]) {
				int tar=M[i][key[p][i]][k].second;
				if(H.count(tar)==0) P2.push_back(tar);
				if(P2.size()>K) break;
			}
			if(P2.size()>K) continue;
			
			H.insert(p);
			if(can(mask^(1<<i),P2,H)) return 1;
			H.erase(p);
		}
	}
	return 0;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>N;
	FOR(i,K) cin>>KX[i]>>KY[i];
	FOR(i,N) cin>>PX[i]>>PY[i];
	
	FOR(i,K) {
		FOR(j,N) {
			int g=__gcd(abs(PX[j]-KX[i]),abs(PY[j]-KY[i]));
			key[j][i]={(PX[j]-KX[i])/g,(PY[j]-KY[i])/g};
			ll v=(PX[j]-KX[i])*(PX[j]-KX[i])+(PY[j]-KY[i])*(PY[j]-KY[i]);
			M[i][key[j][i]].push_back({v,j});
		}
		FORR(r,M[i]) {
			sort(ALL(r.second));
			x = 0;
			FORR(e,r.second) id[e.second][i]=x++;
		}
	}
	
	int ret=0;
	FOR(i,N) ret += can((1<<K)-1,vector<int>(1,i),set<int>());
	cout<<ret<<endl;
}

まとめ