Google Code Jam 2010 Round 2 : C. Bacteria

本番Smallしか解けていないので、復習してみた。
http://code.google.com/codejam/contest/635102/dashboard#s=p2&a=3

Smallは問題文をそのままシミュレートすれば解け、自分もそうした。
Largeは点が100万とか行くのでシミュレートは無理。

細かい証明はAnalysisに任せるけど、解き方としては点同志を上下左右および右上・左下方向で連結し、その点集合の消滅までの時間は(X最大値)+(Y最大値)-(X+Yの最小値)+1となる。
これは小さな長方形や、右下が欠けた形を考えると推測できる。
また、最初離れている図形同士が途中でくっつくこともない。

あとは、点を全部連想配列に入れ、上記手順で連結して時間を求めればよい。
基本的に図形の角の点が最大値や最小値計算の対象となるので、長方形内の点全部を対象とする必要はなく、輪郭だけ対象にしても良い。
でも２割ぐらいしか早くならなかったけどね。

全部の点を連想配列に入れた人もいれば、長方形同士の重なりを検出し、各長方形や重なった長方形の角の点だけ計算してる人もいるね。
後者の方が計算量少ないかと思ったけど、重なり検出がO(長方形数^2)だし、長方形数の上限と点の上限を考えるとあまり変わらないか。

typedef unsigned long long u64;
int R,N;
int X[1000002],Y[1000002],vis[1000002];
map<u64,int> points;
int maxx, maxy,minxy;

u64 key(u64 x,u64 y) {
	return x*1000005 + y;
}

void bfs(int v) {
	deque<int> q;
	int dx[]={-1,1,0,0,-1,1};
	int dy[]={0,0,-1,1,1,-1};
	
	
	vis[v]=1;
	q.push_back(v);
	while(!q.empty()) {
		int nv = q.front();
		q.pop_front();
		points.erase(nv);
		
		if(X[nv]>maxx) maxx=X[nv];
		if(Y[nv]>maxy) maxy=Y[nv];
		if(X[nv]+Y[nv]<minxy) minxy = X[nv]+Y[nv];
		
		int loop;
		FOR(loop,6) {
			int tx = X[nv]+dx[loop];
			int ty = Y[nv]+dy[loop];
			if(points.find(key(tx,ty))==points.end()) continue;
			int nnv = points[key(tx,ty)];
			if(vis[nnv]==1) continue;
			vis[nnv]=1;
			q.push_back(nnv);
		}
	}
	
	
}

void solve(int _loop) {
	int i,j,k,result,dir,ok,fstate,up,x,y;
	double br,tb1,tb2,start,end;
	int x1,x2,y1,y2,lx,ly;
	
	ly=0;lx=0;
	GET1(&R);
	
	points.clear();
	N=0;
	FOR(i,R) {
		GET2(&x1,&y1);
		GET2(&x2,&y2);
		
		for(y=y1;y<=y2;y++){
			for(x=x1;x<=x2;x++){
				if(x!=x1 && x!=x2 && y!=y1 && y!=y2) continue;
				if(points.find(key(x,y))==points.end()) {
					X[N]=x;
					Y[N]=y;
					points.insert(make_pair(key(x,y),N));
					N++;
				}
			}
		}
	}
	ZERO(vis);
	
	result=0;
	FOR(i,N) {
		if(vis[i]) continue;
		maxx=X[i];
		maxy=Y[i];
		minxy = X[i]+Y[i];
		bfs(i);
		j = maxx+maxy-minxy+1;
		if(j>result) result=j;
	}
	
	_PE("Case #%d: %d\n",_loop,result);
}

まとめ

実装の手間の割に25ptと配点が大きい。
法則に気づくまでが勝負ということか。
本番はここまでシンプルに法則を導けなかったな…。