kmjp's blog

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

Codeforces #499 Div1 E. Store

Codeforces

苦戦したけど通せてよかった。
http://codeforces.com/contest/1010/problem/E

問題

X*Y*Zのサイズの３次元グリッドがある。
このうちある直方体区間が有効であるものとする。

ここで、N個の有効区間内のセルと、M個の有効区間外のセルが与えられる。
これらの条件を満たす有効区間が存在するか判定せよ。
有効の場合、さらにK個のセルが与えられる。
各セルが有効区間内・区間外・どちらもあり得る、のいずれか判定せよ。

解法

まずN個を囲う最小の直方体は確実に有効区間の一部である。
よってM個の有効区間外のセルがその外側にあることを判定しよう。

次にK個のセルの問題である。
上述の最小の直方体内にあれば確実に有効区間内である。

それ以外の場合、まずそのセルは有効区間外であり得る。
ただ有効区間内であり得るかどうかは別途判定しなければならない。
「このセルと有効区間の直方体を囲う直方体を考えると、M個の有向区間外のセルも１個以上含んでしまう」という場合、そのセルは有効区間内にはなりえない。
逆にそうでなければ有効区間内にもなりえる。

残る問題は「このセルと有効区間の直方体を囲う直方体を考えると、M個の有向区間外のセルも１個以上含んでしまう」である。
まず、問題をシンプルにするためX,Y,Z座標いずれもN個を囲う最小直方体に該当する部分を点に圧縮しよう。
そうすると最小直方体が点になる。

あとはその点を原点として８つの象限ごとに考えればよくなる。
これには平面(立体？)走査を用いる。
例えば、直方体を圧縮した点を原点としたとき、M個およびK個のセルのうち、X,Y,Z座標が非負の物を考えよう。
これらのセルを、Z座標の小さい順に走査していく。
(0,∞)と走査済みのM個のセルと(∞,0)を囲う図形の外側にK個のセルが来てしまった場合、そのセルを有効区間に含めるには走査済みのM個のセルを含まざるを得ないので、有効区間にはなりえない。
この判定は、凸図形を管理するmap 1個があればよく、複雑なデータ構造は不要である。

int X,Y,Z,N,M,K;
int L[3],R[3];
int OK[101010][3],NG[101010][3],Q[101010][3];

int ret[101010];
vector<pair<int,int>> query[8];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d%d%d%d",&X,&Y,&Z,&N,&M,&K);
	R[0]=R[1]=R[2]=1;
	L[0]=X;
	L[1]=Y;
	L[2]=Z;
	FOR(i,N) {
		scanf("%d%d%d",&OK[i][0],&OK[i][1],&OK[i][2]);
		FOR(j,3) L[j]=min(L[j],OK[i][j]),R[j]=max(R[j],OK[i][j]);
	}
	FOR(i,M) {
		scanf("%d%d%d",&NG[i][0],&NG[i][1],&NG[i][2]);
		int ok=0;
		FOR(j,3) {
			if(NG[i][j]<L[j] || R[j]<NG[i][j]) ok=1;
			if(NG[i][j]>R[j]) NG[i][j]-=R[j]-L[j];
			else if(NG[i][j]>=L[j]) NG[i][j]=L[j];
		}
		if(ok==0)  return _P("INCORRECT\n");
		
		FOR(j,8) {
			int ok=1;
			FOR(x,3) {
				y=(j>>x)&1;
				if(y==0 && NG[i][x]>L[x]) ok=0;
				if(y==1 && NG[i][x]<L[x]) ok=0;
			}
			if(ok) {
				if(j&4) query[j].push_back({NG[i][2],i});
				else query[j].push_back({Z+1-NG[i][2],i});
			}
		}
		
	}
	FOR(i,K) {
		scanf("%d%d%d",&Q[i][0],&Q[i][1],&Q[i][2]);
		ret[i]=1;
		FOR(j,3) {
			ret[i]&=(L[j]<=Q[i][j]&&Q[i][j]<=R[j]);
			if(Q[i][j]>R[j]) Q[i][j]-=R[j]-L[j];
			else if(Q[i][j]>=L[j]) Q[i][j]=L[j];
		}
		if(ret[i]==0) {
			FOR(j,8) {
				int ok=1;
				FOR(x,3) {
					y=(j>>x)&1;
					if(y==0 && Q[i][x]>L[x]) ok=0;
					if(y==1 && Q[i][x]<L[x]) ok=0;
				}
				if(ok) {
					if(j&4) query[j].push_back({Q[i][2],100000+i});
					else query[j].push_back({Z+1-Q[i][2],100000+i});
				}
			}
		}
	}
	
	FOR(i,8) {
		map<ll,ll> mp;
		mp[0]=1000000;
		mp[1000000]=0;
		sort(ALL(query[i]));
		FORR(z,query[i]) {
			j=z.second;
			if(j<100000) {
				x=NG[j][0];
				y=NG[j][1];
				if((i&1)==0) x=X+1-x;
				if((i&2)==0) y=Y+1-y;
				auto it=mp.lower_bound(x+1);
				it--;
				if(it->second>=y) {
					mp[x]=y;
					while(1) {
						it=mp.lower_bound(x+1);
						if(it->second<y) break;
						mp.erase(it);
					}
				}
			}
			else {
				j-=100000;
				x=Q[j][0];
				y=Q[j][1];
				if((i&1)==0) x=X+1-x;
				if((i&2)==0) y=Y+1-y;
				auto it=mp.lower_bound(x+1);
				it--;
				if(it->second<=y) ret[j]=2;
			}
		}
		
	}
	
	_P("CORRECT\n");
	FOR(i,K) {
		if(ret[i]==1) _P("OPEN\n");
		if(ret[i]==2) _P("CLOSED\n");
		if(ret[i]==0) _P("UNKNOWN\n");
	}
	
	
}

まとめ

座標圧縮を思いつけたのは良かった。
これがなければ解けなかったので…。