kmjp's blog

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

Google Code Jam 2015 Round 1A : C. Logging

GCJ

これは解けて良かった。
https://code.google.com/codejam/contest/4224486/dashboard#s=p2

問題

二次元座標上N個の座標が与えられる。

各点がこれらの点の凸包の頂点もしくは辺上に来るためには、それぞれ何個他の点を消さなければならないか答えよ。

解法

計算量毎に書いていく。

Small解:O(2^N*N*logN)

幸い、SmallはNが15と小さい。
そこで、残す点を2^15通り総当たりし、それぞれ凸包を求め、その凸包の頂点または辺上にある点に対して消した点の最小値を更新していけば良い。
頂点だけはなく辺上も対象となるので、凸包を求めるときは注意。

template<class C> C veccross(pair<C,C> p1,pair<C,C> p2,pair<C,C> p3) {
	p3.first-=p1.first;p2.first-=p1.first;
	p3.second-=p1.second;p2.second-=p1.second;
	return p3.first*p2.second-p2.first*p3.second;
}

template<class C> vector<int> convex_hull(vector< pair<C, C> >& vp) {
	vector<pair<pair<C, C>, int> > sorted;
	vector<int> res;
	int i,k=0,rb;
	
	if(vp.size()<=2) {
		if(vp.size()>=1) res.push_back(0);
		if(vp.size()>=2 && vp[0]!=vp[1]) res.push_back(1);
		return res;
	}
	
	FOR(i,vp.size()) sorted.push_back(make_pair(vp[i],i));
	sort(sorted.begin(),sorted.end());
	
	res.resize(vp.size()*2);
	/* bottom */
	FOR(i,vp.size()) {
		while(k>1 && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<0) k--;
		res[k++]=sorted[i].second;
	}
	/* top */
	for(rb=k, i=vp.size()-2;i>=0;i--) {
		while(k>rb && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<0) k--;
		res[k++]=sorted[i].second;
	}
	res.resize(k-1);
	return res;
}

int N;
ll X[3030],Y[3030];
int ma[3030];


void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i], ma[i]=2;
	
	for(int mask=0;mask<1<<N;mask++) if(__builtin_popcount(mask)>2) {
		vector<int> P;
		vector<pair<ll,ll> > Pos;
		FOR(x,N) if(mask&(1<<x)) P.push_back(x), Pos.emplace_back(X[x],Y[x]);
		}
		vector<int> V=convex_hull(Pos);
		FORR(r,V) ma[P[r]]=max(ma[P[r]],__builtin_popcount(mask));
	}
	
	_P("Case #%d:\n",_loop);
	FOR(i,N) _P("%d\n",N-ma[i]);
}

Medium解:O(N^3)

Small解ではLargeを時間内に解けないので、高速化することを考える。

2頂点X-Yを結ぶ線分が凸包の一部辺を構成する場合を仮定する。
この線分が凸包の辺となるためには、X-Yを延長した直線を境界として、どちらかにある点すべてを削除しなければならない。
X-Yを延長した直線状にある点は無視してよい(今回凸包の頂点だけでなく、辺上に残ることが許されているため)

よって(X,Y以外の)各Zを総当たりし、X-Yを延長した直線のどちらかにあるかを求めて、少ない側の頂点数を削除候補とし、Yを凸包の境界に置くための最小削除頂点数を更新する。
ただ、これはO(N^3)なのでまだLargeには間に合わない。

template<class C> C veccross(pair<C,C> p1,pair<C,C> p2,pair<C,C> p3) {
	p3.first-=p1.first;p2.first-=p1.first;
	p3.second-=p1.second;p2.second-=p1.second;
	return p3.first*p2.second-p2.first*p3.second;
}

int N;
pair<ll,ll> P[3030];
int ma[3030];


void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>P[i].first>>P[i].second,ma[i]=N;
	if(N<=2) FOR(i,N) ma[i]=0;
	
	FOR(i,N) {
		FOR(x,N) if(i!=x) {
			int pl=0,mi=0;
			
			FOR(y,N) if(y!=i && y!=x) {
				ll cr=veccross(P[i],P[x],P[y]);
				if(cr>0) pl++;
				if(cr<0) mi++;
			}
			ma[i]=min(ma[i],min(pl,mi));
		}
	}
	
	_P("Case #%d:\n",_loop);
	FOR(i,N) _P("%d\n",ma[i]);
}

Large解:O(N^2*logN)

頂点X-Yを延長した直線を境界として、残りの頂点がどちらにあるかを数えるのを高速化したい。
X→Yへの偏角をarg(X,Y)とする。

X-Yを延長した直線に対し、以下を満たす頂点p,qの数を求めれば、min(p,q)がX-Yを凸包の境界にする際削除する点の数になる。

  • arg(X,Y)＜arg(X,p)＜arg(X,Y)+π
  • arg(X,Y)+π＜arg(X,q)＜arg(X,Y)+2π

これは先に各頂点Zに対してarg(X,Z)を列挙しておいてソートしてしまえば、尺取法なりlower_boundなりでYごとにp,qの数を求められる。
以下はlower_boundを使っているのでちょっと重くて5秒以上かかるケースもあった。
尺取法ならもう少し軽くなるかも。

int N;
pair<ll,ll> P[3030];
int ma[3030];
double deg[3030];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	double pi=acos(-1);
	cin>>N;
	FOR(i,N) cin>>P[i].first>>P[i].second,ma[i]=N;
	if(N<=2) FOR(i,N) ma[i]=0;
	
	FOR(i,N) {
		vector<double> V;
		FOR(x,N) if(i!=x) {
			ll dx=P[x].first-P[i].first;
			ll dy=P[x].second-P[i].second;
			ll g=__gcd(abs(dx),abs(dy));
			deg[x]=atan2(dx/g,dy/g);
			if(deg[x]<0) deg[x]+=2*pi;
			V.push_back(deg[x]);
			V.push_back(deg[x]+2*pi);
			V.push_back(deg[x]+4*pi);
		}
		sort(V.begin(),V.end());
		FOR(x,N) if(i!=x) {
			int pl=lower_bound(V.begin(),V.end(),deg[x]+pi)-lower_bound(V.begin(),V.end(),deg[x]+1e-10);
			int mi=lower_bound(V.begin(),V.end(),deg[x]+2*pi)-lower_bound(V.begin(),V.end(),deg[x]+pi+1e-10);
			ma[x]=min(ma[x],min(pl,mi));
		}
	}
	
	_P("Case #%d:\n",_loop);
	FOR(i,N) _P("%d\n",ma[i]);
}

まとめ

最初O(N^3)解法が思い浮かんだものの、安全を期して手っ取り早そうなO(2^N*N*logN)解法に行ってしまった。
でも終わってみるとO(N^3)解法が一番シンプルだよなぁ。