kmjp's blog

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

Codeforces #371 Div1 D. Animals and Puzzle

Codeforces

知らないデータ構造が出て勉強になった。
http://codeforces.com/contest/713/problem/D

問題

N*Mのグリッドが与えられる。各マスは白黒に塗り分けられている。
このグリッドに対し、T個のクエリが与えられる。
各クエリは、グリッド中の矩形領域で構成される。矩形内で、最大サイズの塗りつぶされた正方形を答えよ。

解法

二分探索と2D Sparse Tableで解く。(2D SegTreeでも解けるかもしれないが計算量的に不安)

まず、各セル(x,y)に対し、そのセルを左上とする最大の正方形サイズS(x,y)を求めておこう。
事前に累積和を求めておくと尺取法の要領でこの部分はO(NM)で計算できる。

クエリの範囲を(x1,y1)-(x2,y2)とする。
この範囲にサイズaの正方形があるのなら、(x1,y1)-(x2-(a-1),y2-(a-1))の範囲に、S(x,y)≧aとなる(x,y)があればよい。
これは矩形範囲内の値の最大値を求めることに相当する。

自分は知らなかったが、2D Sparse Tableというデータ構造を用いると、前処理でO(NM*logN*logM)かかるがクエリをO(1)で解くことができる。
2D SegTreeよりメモリを食うが、今回はTが大きいのでこちらを用いた方が無難。
http://codeforces.com/blog/entry/45485

あとはsに対しては二分探索すればよい。

template<class V,int NV> class RMQ_2D {
private:
	V table[NV][NV][1<<NV][1<<NV];
	int LG[1<<NV];
	int NV2;
public:
	static V const def=-1<<30;
	V comp(V l,V r){ return max(l,r);};
	RMQ_2D() {
		int i,j,x,y;
		NV2=1<<NV;
		for(i=2;i<	NV2;i++) LG[i]=LG[i/2]+1;
		FOR(i,NV) FOR(j,NV) FOR(x,NV2) FOR(y,NV2) table[i][j][x][y]=def;
	}
	void set(int x,int y,V v){ table[0][0][x][y]=v;}
	void build() {
		int i,j,x,y;
		FOR(i,NV) FOR(j,NV) FOR(x,NV2) FOR(y,NV2) {
			if(i<NV-1) table[i+1][j][x][y]=comp(table[i][j][x][y],(x+(1<<i)<NV2)?table[i][j][x+(1<<i)][y]:def);
			if(j<NV-1) table[i][j+1][x][y]=comp(table[i][j][x][y],(y+(1<<j)<NV2)?table[i][j][x][y+(1<<j)]:def);
		}
	}
	V query(int L,int R,int T,int B) { //[L,R), [T,B)
		L=max(0,L), R=min(R,NV2), T=max(0,T), B=min(B,NV2);
		if(R<=L || B<=T) return def;
		int WL=LG[R-L],HL=LG[B-T];
		return comp(comp(table[WL][HL][L][T],table[WL][HL][R-(1<<WL)][T]),
			comp(table[WL][HL][L][B-(1<<HL)],table[WL][HL][R-(1<<WL)][B-(1<<HL)]));
	}
	
};

RMQ_2D<int,10> rmq;
int H,W,Q;
int A[1010][1010];
int S[2010][2010];
int T[1010][1010];

int yes(int y,int x,int t) {
	return (S[y+t][x+t]-S[y+t][x]-S[y][x+t]+S[y][x])==t*t;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&H,&W);
	FOR(y,H) FOR(x,W) {
		scanf("%d",&A[y][x]);
		S[y+1][x+1]=S[y+1][x]+S[y][x+1]-S[y][x]+A[y][x];
	}
	FOR(y,H) FOR(x,W) {
		if(A[y][x]) {
			T[y][x]=1;
			if(y&&x) T[y][x]=max(T[y][x],T[y-1][x-1]-1);
			while(yes(y,x,T[y][x]+1)) T[y][x]++;
		}
		rmq.set(x,y,T[y][x]);
	}
	rmq.build();
	
	scanf("%d",&Q);
	while(Q--) {
		int L,R,T,B;
		scanf("%d%d%d%d",&L,&T,&R,&B);
		L--,T--;
		x=0;
		for(i=9;i>=0;i--) {
			y=x+(1<<i);
			if(rmq.query(T,B-(y-1),L,R-(y-1))>=y) x=y;
		}
		_P("%d\n",x);
	}
	
	
}

まとめ

これみんな知ってるテクだったのか…。