kmjp's blog

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

Bayan 2015 Contest Warmup: F. Meta-universe

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

問題

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

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

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

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

解法

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

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

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

  • 1番左のX座標
  • 1番右のX座標
  • 1番上のY座標
  • 1番下のY座標
  • 2番目に左のX座標
  • 2番目に右のX座標
  • 2番目に上のY座標
  • 2番目に下の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;
}

まとめ

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

広告を非表示にする