kmjp's blog

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

Codeforces #567 Div2 E. A Story of One Country (Hard)

このテクは勉強になった。
https://codeforces.com/contest/1181/problem/E2

問題

グリッド上にN個の矩形領域が与えられる。
これらの領域は重複はしていないが、全領域の和をとってもグリッド全体になるとは限らない。

グリッドをN個の長方形に分割したとき、これらの矩形が1個ずつ入るようにできるか。

解法

基本的には、複数の矩形領域が含まれる長方形があったら、どこか縦か横に二分割して分離していく、という方針。
ただうまく分割位置を探さないと、O(N^2)かかりかねない。

そこで分割位置の探し方だが、上から下や左から右の一方通行ではなく、上下左右4方向から徐々に狭めていく。
こうすると分割する際に、探索時間が長いほど均等に二分割され今後の探索が高速になる。

int N;
int X1[101010],X2[101010],Y1[101010],Y2[101010];

int dfs(set<pair<int,int>>& L, set<pair<int,int>>& R,set<pair<int,int>>& U,set<pair<int,int>>& D) {
	if(L.size()<=1) return 1;
	auto Lit=L.begin();
	auto Rit=R.begin();
	auto Dit=D.begin();
	auto Uit=U.begin();
	int Llim=X2[Lit->second];
	int Rlim=X1[Rit->second];
	int Dlim=Y2[Dit->second];
	int Ulim=Y1[Uit->second];
	set<pair<int,int>> L2,R2,U2,D2;
	
	while(1) {
		Lit++;
		Rit++;
		Dit++;
		Uit++;
		if(Lit==L.end()) break;
		
		if(Lit->first>=Llim) {
			auto p=*Lit;
			while(*L.begin()!=p) {
				int x=L.begin()->second;
				L2.insert({X1[x],x});
				R2.insert({-X2[x],x});
				D2.insert({Y1[x],x});
				U2.insert({-Y2[x],x});
				L.erase({X1[x],x});
				R.erase({-X2[x],x});
				D.erase({Y1[x],x});
				U.erase({-Y2[x],x});
			}
			return dfs(L,R,U,D)&&dfs(L2,R2,U2,D2);
		}
		if(Dit->first>=Dlim) {
			auto p=*Dit;
			while(*D.begin()!=p) {
				int x=D.begin()->second;
				L2.insert({X1[x],x});
				R2.insert({-X2[x],x});
				D2.insert({Y1[x],x});
				U2.insert({-Y2[x],x});
				L.erase({X1[x],x});
				R.erase({-X2[x],x});
				D.erase({Y1[x],x});
				U.erase({-Y2[x],x});
			}
			return dfs(L,R,U,D)&&dfs(L2,R2,U2,D2);
		}
		if(-Rit->first<=Rlim) {
			auto p=*Rit;
			while(*R.begin()!=p) {
				int x=R.begin()->second;
				L2.insert({X1[x],x});
				R2.insert({-X2[x],x});
				D2.insert({Y1[x],x});
				U2.insert({-Y2[x],x});
				L.erase({X1[x],x});
				R.erase({-X2[x],x});
				D.erase({Y1[x],x});
				U.erase({-Y2[x],x});
			}
			return dfs(L,R,U,D)&&dfs(L2,R2,U2,D2);
		}
		if(-Uit->first<=Ulim) {
			auto p=*Uit;
			while(*U.begin()!=p) {
				int x=U.begin()->second;
				L2.insert({X1[x],x});
				R2.insert({-X2[x],x});
				D2.insert({Y1[x],x});
				U2.insert({-Y2[x],x});
				L.erase({X1[x],x});
				R.erase({-X2[x],x});
				D.erase({Y1[x],x});
				U.erase({-Y2[x],x});
			}
			return dfs(L,R,U,D)&&dfs(L2,R2,U2,D2);
		}
		Llim=max(Llim,X2[Lit->second]);
		Rlim=min(Rlim,X1[Rit->second]);
		Dlim=max(Dlim,Y2[Dit->second]);
		Ulim=min(Ulim,Y1[Uit->second]);
	}
	
	return 0;
	
}

int dfs(vector<int>& A) {
	if(A.size()<=1) return 1;
	
	int i,R;
	vector<pair<int,int>> C;
	//X
	FORR(a,A) C.push_back({X1[a],X2[a]});
	sort(ALL(C));
	R=C[0].second;
	
	for(i=1;i<C.size();i++) {
		if(C[i].first>=R) {
			vector<int> S,T;
			
			FORR(a,A) {
				if(X2[a]<=C[i].first) S.push_back(a);
				else T.push_back(a);
			}
			return dfs(S)&dfs(T);
		}
		else {
			R=max(R,C[i].second);
		}
	}
	C.clear();
	// Y
	FORR(a,A) C.push_back({Y1[a],Y2[a]});
	sort(ALL(C));
	R=C[0].second;
	for(i=1;i<C.size();i++) {
		if(C[i].first>=R) {
			vector<int> S,T;
			
			FORR(a,A) {
				if(Y2[a]<=C[i].first) S.push_back(a);
				else T.push_back(a);
			}
			return dfs(S)&dfs(T);
		}
		else {
			R=max(R,C[i].second);
		}
	}
	
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	set<pair<int,int>> L,R,U,D;
	FOR(i,N) {
		cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
		L.insert({X1[i],i});
		R.insert({-X2[i],i});
		D.insert({Y1[i],i});
		U.insert({-Y2[i],i});
	}
	
	if(dfs(L,R,U,D)) _P("YES\n");
	else _P("NO\n");
	
}

まとめ

似たテク他にもどこかで見た気がするんだよなー。