第5回 ドワンゴからの挑戦状 予選 : D - Square Rotation

うーむ、なぜこれが本番中出せなかったか。
https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_d

問題

2次元座標中でN個の異なる座標の格子点が与えられる。
それらの位置にはぬいぐるみがあるとする。
ここで、以下の処理を行う。

定数Dが与えられる。任意の(x,y)を選択し、(x,y)→(x+D,y)→(x+D,y+D)→(x,y+D)→(x,y)と4つの点の載っているぬいぐるみの位置を回転する。

全ぬいぐるみができるだけ狭い正方形領域内に収まるようにしたい。
1辺の最小サイズを求めよ。

解法

回転処理は、結局各点をDずつ上下左右に移動できることを意味する。
そこで、まず最初に各ぬいぐるみの位置(Xi,Yi)を(Xi%D,Yi%D)で分類して各組におけるぬいぐるみの数を求めよう。

そうすると、まず組内のぬいぐるみを配置する最小サイズが決まる。
組内のぬいぐるみの数の最大値をCとすると、C≦R^2を満たす最小のRを考えると最小で1辺(R-1)Dの正方形が必要となる。

次に、各組のぬいぐるみ数AをこのRに対し分類する。

• A≦(R-1)^2 の場合、どこかに1辺(R-1)Dの正方形を置けば、必ずA個を置ききることができるので以後このような組は無視してよい。
• (R-1)^2＜A≦R*(R-1) の場合、(R-1)*(R-2)個のぬいぐるみを配置できる長方形領域の確保が必要である。
• R*(R-1)＜A≦R^2 の場合、(R-1)*(R-1)個のぬいぐるみを配置できる正方形領域の確保が必要である。

正方形の左下の点(x,y)を0≦x＜D、0≦y＜Dで総当たりし、それぞれの場合の正方形の最小サイズを求めよう。
最低(R-1)Dいることは確定していて、RDは不要なことがわかっている。
そこで1辺L=(R-1)*D+aとしてaを求める。このaを二分探索しよう。

• (x,y)-(x+a-1,y+a-1)の範囲の組(座標がDを超える場合mod Dを取る)は上記3つどのパターンでも構わない。
• (x,y+a-1)-(x+a-1,y+D-1)および(x+a-1,y)-(x+D-1,y+a-1)の範囲の組は上2つのパターンでなければならない。
• (x+a-1,y+a-1)-(x+D-1,y+D-1)の範囲の組は最上段のパターンでなければならない。

各組の登場回数に対し2次元の累積和を取っておくと、上記判定はO(1)で行える。
あとは各左下隅(x,y)に対するLの最小値を取ろう。

int N,D;
int X[101010];
int Y[101010];

int A[2][2110][2110];
int S[2][2110][2110];
int num[2020][2020];

int sum(int type,int x,int y,int d) {
	return S[type][x+d][y+d]-S[type][x+d][y]-S[type][x][y+d]+S[type][x][y];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D;
	int R=0;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		num[X[i]%D][Y[i]%D]++;
		R=max(R,num[X[i]%D][Y[i]%D]);
	}
	
	x=1;
	while(x*x<R) x++;
	R=x;
	
	FOR(x,D) FOR(y,D) {
		if(num[x][y]<=(R-1)*(R-1)) {
			continue;
		}
		else if(num[x][y]<=R*(R-1)) {
			A[1][x][y]=1;
		}
		else {
			A[0][x][y]=1;
		}
	}
	FOR(i,2) FOR(x,2*D+1) FOR(y,2*D+1) {
		if(x) S[i][x][y]+=S[i][x-1][y];
		if(y) S[i][x][y]+=S[i][x][y-1];
		if(x&&y) {
			S[i][x][y]-=S[i][x-1][y-1];
			S[i][x][y]+=A[i][(x-1)%D][(y-1)%D];
		}
	}
	
	int mi=101010;
	FOR(x,D) FOR(y,D) {
		int cur=D;
		for(i=10;i>=0;i--) if(cur-(1<<i)>=1) {
			j=cur-(1<<i);
			if(sum(0,x,y,D)!=sum(0,x,y,j)) continue;
			if(sum(1,x+j,y+j,D-j)) continue;
			cur-=1<<i;
		}
		
		mi=min(mi,cur);
	}
	
	cout<<mi-1+(R-1)*D<<endl;
	
	
}

まとめ

本番は複雑なデータ構造で解こうとして失敗。