kmjp's blog

競技プログラミング参加記です

TopCoder SRM 703 Div1 Medium CoastGuard

これは気づいてしまえばすんなり。
https://community.topcoder.com/stat?c=problem_statement&pm=14458

問題

2次元座標上、X軸上にN個の頂点があり、各頂点iは(D[i],0)に配置されている。
また、Y座標が正の範囲にN個の頂点があり、各頂点jは(X[j],Y[j])に配置されている。

前者の頂点と後者の頂点を1:1で対応付けることを考える。
単純に考えればその組み合わせはN!とおりである。
このうち、対応づく2つの点を結ぶ線分を計N個作った場合、それらが互いに交差しないような組み合わせは何通りとなるか。

解法

前者の頂点をD[i]の昇順に並べ替えておこう。
逆に後者はY[j]の降順に並べ替えておく。

後者の頂点のY[j]の大きい順に、対応する前者の頂点iを決めることを考える。
この時、(D[i],0)-(X[j],Y[j])の間に線分を引くと、残された前者および後者の頂点群は、この線分で互いに左右に分けられた範囲でのみ対応付けすることができる。

よって以下のDPを考え、L≦i≦RとS中y座標が最大な頂点jの組み合わせを総当たりしていけばよい。
f(L,R,S) := 前者の頂点L~R番までと、後者の頂点集合Sとで条件を満たす対応付けの数
f(0,N-1,{0, ... N-1})が解。

このDPは一見Sが2^N通りあって状態数でO(N^2*2^N)、計算量でO(N^3*2^N)ありそうだが、実際はf(L,R,S)が非ゼロになるようなSはそんなにないため、適切に枝刈りしていけば高速に終わる。

ll mo=1000000007;
map<vector<int>,ll> memo[55][55];

class CoastGuard {
	public:
	int N;
	vector<int> D,X,Y;
	vector<int> V;
	
	ll dpdp(int L,int R,vector<int> V) {
		if(V.size()<=1) return 1;
		if(memo[L][R].count(V)) return memo[L][R][V];
		ll ret=0;
		int i,j;
		for(i=L;i<=R;i++) {
			vector<int> left;
			vector<int> right;
			FOR(j,V.size()-1) {
				int side=(X[V[j]]-D[i])*Y[V.back()]-(X[V.back()]-D[i])*Y[V[j]];
				if(side==0) break;
				if(side<0) left.push_back(V[j]);
				if(side>0) right.push_back(V[j]);
			}
			if(i-L==left.size() && R-i==right.size()) ret += dpdp(L,i-1,left)*dpdp(i+1,R,right);
			//_P("select %d-%d %d (%d,%d) %lld L%d R%d\n",L,R,i,X[V.back()],Y[V.back()],ret,left.size(),right.size());
		}
		
		return memo[L][R][V] = ret % mo;
	}
	
	int count(vector <int> d_, vector <int> x_, vector <int> y_) {
		int i,j;
		D=d_;
		N=D.size();
		
		vector<pair<int,int>> P;
		V.clear();
		X.clear();
		Y.clear();
		
		sort(ALL(D));
		
		FOR(i,N) P.push_back({y_[i],x_[i]}), V.push_back(i);
		sort(ALL(P));
		FOR(i,N) X.push_back(P[i].second),Y.push_back(P[i].first);
		
		FOR(i,N) FOR(j,N) memo[i][j].clear();
		
		return dpdp(0,N-1,V);
		
	}
}

まとめ

左端から決めていこうとするとうまくいかないが、上から決めていくと残りの頂点群がきれいに左右に分かれるのがコツ。