MemSQL start[c]up Round 2 : D. Rectangles and Square

典型っぽくてRound1の方が好きかも。
http://codeforces.com/contest/335/problem/D

問題

２次元座標上で、格子点(X[i],Y[i])を頂点として辺がXY軸に平行なN個の長方形が与えられる。
これらの長方形は互いに共通部分を持たない。

この長方形のうち幾つかを選び、正方形を作りたい。
正方形の中のすべての領域がいずれかの長方形に含まれ、かつすべての長方形は全体が正方形に含まれるか全体が正方形外にあるような正方形は作れるかどうか判定せよ。

解法

X,Yの上限をKとする。
EditorialではO(N*logN)の解法を紹介しているが、自分はO(NK)で通った。

まず前処理として、正方形の中身が埋まっているか判定するため、２次元座標を1x1サイズのグリッドで分割し、各セルが長方形に含まれるか求めたうえで累積和を求める。

さらに、「あるセルとその下のセルが同じ長方形に含まれる」または「あるセルとその右のセルが同じ長方形に含まれる」かどうかを求めておき、こちらも同様に累積和を求めておく。

あとは各長方形が正方形の左下に来ると仮定し、正方形のサイズwを1～Kの範囲で総当たりし、以下を全部満たせば条件を満たす正方形が作れる。
各判定は累積和を使えばO(1)なので、全体でO(NK)。

• (X[i],Y[i])-(X[i]+W,Y[i]+W)の範囲のセルは長方形に含まれる。
• (X[i]+i,Y[i]-1)と(X[i]+i,Y[i])は各iにおいて同一の長方形に含まれない。
• (X[i]-1,Y[i]+i)と(X[i],Y[i]+i)は各iにおいて同一の長方形に含まれない。
• (X[i]+i,Y[i]+w-1)と(X[i]+i,Y[i]+w)は各iにおいて同一の長方形に含まれない。
• (X[i]+w-1,Y[i]+i)と(X[i]+w,Y[i]+i)は各iにおいて同一の長方形に含まれない。

int N;
int X1[100050],X2[100050],Y1[100050],Y2[100050];
int A[3005][3005],ID[3005][3005],S[3005][3005];
int ngv[3005][3005],ngh[3005][3005];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	MINUS(ID);
	FOR(i,N) {
		cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
		X1[i]++;Y1[i]++;X2[i]++;Y2[i]++;
		FOR(x,X2[i]-X1[i]) FOR(y,Y2[i]-Y1[i]) A[y+Y1[i]][x+X1[i]]=1, ID[y+Y1[i]][x+X1[i]]=i;
	}
	FOR(y,3003) {
		FOR(x,3003) S[y+1][x+1]=S[y+1][x]+A[y][x];
		FOR(x,3003) S[y+1][x+1]+=S[y][x+1];
	}
	FOR(y,3003) FOR(x,3003) ngh[y][x]=(x?ngh[y][x-1]:0)+(ID[y][x]==ID[y+1][x] && ID[y][x]!=-1);
	FOR(y,3003) FOR(x,3003) ngv[y][x]=(y?ngv[y-1][x]:0)+(ID[y][x]==ID[y][x+1] && ID[y][x]!=-1);
	
	FOR(i,N) {
		for(int w=1;;w++) {
			if(S[Y1[i]+w][X1[i]+w]-S[Y1[i]+w][X1[i]]-S[Y1[i]][X1[i]+w]+S[Y1[i]][X1[i]]<w*w) break;
			int ng=0;
			if(ngv[Y1[i]-1][X1[i]-1]!=ngv[Y1[i]+w-1][X1[i]-1]) break;
			if(ngh[Y1[i]-1][X1[i]-1]!=ngh[Y1[i]-1][X1[i]+w-1]) break;
			if(ngv[Y1[i]-1][X1[i]+w-1]!=ngv[Y1[i]+w-1][X1[i]+w-1]) continue;
			if(ngh[Y1[i]+w-1][X1[i]-1]!=ngh[Y1[i]+w-1][X1[i]+w-1]) continue;
			
			set<int> S;
			FOR(x,w) FOR(y,w) S.insert(ID[Y1[i]+y][X1[i]+x]+1);
			_P("YES %d\n",S.size());
			ITR(s,S) _P("%d ",*s);
			_P("\n");
			return;
		}
	}
	_P("NO\n");
}

まとめ

O(NK)はちょっと安直解法だったかな…。