Bayan 2015 Contest Warmup : F. Meta-universe

計算量の落とし方が面白い。
http://codeforces.com/contest/475/problem/F

問題

無限に広がる２次元グリッドがあり、うち星が存在するセルの座標(X[i],Y[i])がN個分与えられる。
初期状態ではN個の星が１つの宇宙を作っている。

星の集合Mからなる宇宙は、以下の条件で２つに分割できる。

• 幅１・高さ無限の線を引いたとき、線上にM中の星がないなら、線の左右にある星群それぞれで２つの宇宙を創る。
• 高さ１・幅無限の線を引いたとき、線上にM中の星がないなら、線の上下にある星群それぞれで２つの宇宙を創る。

最大何個まで宇宙を分割できるか。

解法

分割するための線を引く位置の候補は、X座標がX[i]±1の位置に高さ無限の線を引くか、Y座標がY[i]±1の位置に幅無限の線を引くかどちらかである。

ただ、この線を引いたときに他の星が重ならないかどうかを毎回判定するとTLEする。
例えば１回の分割で1個だけ星が別宇宙になる場合、O(N)個の宇宙についてO(N)回判定するのでO(N^2)で間に合わない。

そこで分割順を工夫して、判定にかかる時間を減らしたい。
判定の際、X[i]±1やY[i]±1を端から順に分割可否を判定せず、以下の順で判定する。

• １番左のX座標
• １番右のX座標
• １番上のY座標
• １番下のY座標
• ２番目に左のX座標
• ２番目に右のX座標
• ２番目に上のY座標
• ２番目に下のY座標

…

こうすると、分割後の宇宙について同じX座標・Y座標を繰り返し判定する頻度が減り、TLEを防げる。

int dfs(set<pair<ll,ll> >& XS,set<pair<ll,ll> >& YS) {
	int N=XS.size(),i;
	if(XS.empty()) return 0;
	set<pair<ll,ll> >::iterator xa=XS.begin();
	set<pair<ll,ll> >::iterator ya=YS.begin();
	set<pair<ll,ll> >::iterator xb=XS.end();
	set<pair<ll,ll> >::iterator yb=YS.end();
	set<pair<ll,ll> >::iterator n,n2;
	set<pair<ll,ll> > NXS,NYS;
	
	xb--; yb--;
	
	FOR(i,N-1) {
		set<pair<ll,ll> >::iterator r;
		
		n=xa;n++;
		if(n->first>xa->first+1) {
			for(xa=XS.begin();xa!=n;) {
				NXS.insert(*xa);
				NYS.insert(make_pair(xa->second,xa->first));
				YS.erase(make_pair(xa->second,xa->first));
				XS.erase(xa++);
			}
			return dfs(XS,YS)+dfs(NXS,NYS);
		}
		n=xb;n--;
		if(xb->first>n->first+1) {
			n=xb;
			for(;n!=XS.end();) {
				NXS.insert(*n);
				NYS.insert(make_pair(n->second,n->first));
				YS.erase(make_pair(n->second,n->first));
				XS.erase(n++);
			}
			return dfs(XS,YS)+dfs(NXS,NYS);
		}
		n=ya;n++;
		if(n->first>ya->first+1) {
			for(ya=YS.begin();ya!=n;) {
				NYS.insert(*ya);
				NXS.insert(make_pair(ya->second,ya->first));
				XS.erase(make_pair(ya->second,ya->first));
				YS.erase(ya++);
			}
			return dfs(XS,YS)+dfs(NXS,NYS);
		}
		n=yb;n--;
		if(yb->first>n->first+1) {
			n=yb;
			for(;n!=YS.end();) {
				NYS.insert(*n);
				NXS.insert(make_pair(n->second,n->first));
				XS.erase(make_pair(n->second,n->first));
				YS.erase(n++);
			}
			return dfs(XS,YS)+dfs(NXS,NYS);
		}
		xa++, ya++, xb--, yb--;
	}
	return 1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	ll xx,yy;
	set<pair<ll,ll> > XS,YS;
	
	cin>>i;
	while(i--) {
		cin>>xx>>yy;
		xx+=1e9+1;
		yy+=1e9+1;
		XS.insert(make_pair(xx,yy));
		YS.insert(make_pair(yy,xx));
	}
	cout << dfs(XS,YS) << endl;
}

まとめ

この計算量の落とし方は面白かったな。