Code Formula 2014 本選 : F - 100個の円

面積を見誤って無駄に苦戦。図示したらあっさり。
http://code-formula-2014-final.contest.atcoder.jp/tasks/code_formula_2014_final_f

問題

２次元座標上、(0,0)-(1500,1500)の矩形の範囲の中に、半径1,2,3,...,99,100の円100個を配置せよ。
なお、各円の中心は格子点上になければならず、かつ円同士が交差したり矩形の範囲外に出てはならない。
円同士が接したり矩形の境界に接するのはよい。

解法

100個の円の面積の合計は矩形の範囲の47%と半分以下なので、割とおおざっぱに配置しても間に合う。
以下２つの案を紹介。

一つは４辺の端に合わせて７個ずつ置いていく方法。
以降はそれらの円と重ならないよう、内側の正方形の範囲にまた７個ずつ置いていく。

もう一つは1500x1500の領域を300x300の領域25個に分割し、それぞれ4個ずつ置いていく。
以下は1≦i≦25に対し、半径i, 51-i, 50+i, 101-iの４つの円を角においている。

以下のコードはコメント内は前者、コメント外は後者の座標を100個出力する。

int X[101],Y[101];
void rot(int from,int to) {
	X[to]=750+(750-Y[from]);
	Y[to]=750-(750-X[from]);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	/*
	int ox=0,oy=750,id=104;
	ox=0,oy=750;id=100+4;
	id-=4; X[id]=ox+id, Y[id]=oy; for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy-(100+96);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy+(100+92);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy+(100+92)+(92+88);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy-(100+96)-(96+84);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy-(100+96)-(96+84)-(84+80);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy+(100+92)+(92+88)+(88+76);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	
	ox=200; id=72+4;
	id-=4; X[id]=ox+id, Y[id]=oy; for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy-(72+68);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy+(72+64);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy+(72+64)+(64+60);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy-(72+68)-(68+56);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy-(72+68)-(68+56)-(56+52);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy+(72+64)+(64+60)+(60+48);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);

	ox=200+72*2; id=44+4;
	id-=4; X[id]=ox+id, Y[id]=oy; for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy-(44+40);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy+(44+36);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy+(44+36)+(36+32);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy-(44+40)-(40+32);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy-(44+40)-(40+32)-(32+28);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy+(44+36)+(36+32)+(32+24);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	
	ox=200+72*2+44*2; id=16+4;
	id-=4; X[id]=ox+id, Y[id]=oy; for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy-(16+12);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy+(16+8);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	id-=4; X[id]=ox+id, Y[id]=oy+(16+8)+(8+4);	for(i=1;i<=3;i++) rot(id-(i-1),id-i);
	*/
	
	for(x=0;x<5;x++) for(y=0;y<5;y++) {
		i=x*5+y+1;
		int ox=x*300;
		int oy=y*300;
		X[101-i]=ox+(101-i);
		Y[101-i]=oy+(101-i);
		X[50+i]=ox+300-(50+i);
		Y[50+i]=oy+300-(50+i);
		X[51-i]=ox+300-(51-i);
		Y[51-i]=oy+(51-i);
		X[i]=ox+i;
		Y[i]=oy+300-i;
	}

	for(i=1;i<=100;i++) for(j=i+1;j<=100;j++) {
		if(X[i]==0 || X[j]==0) continue;
		if((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j])<(i*i+j*j)) _P("NG %d %d\n",i,j);
	}
	FOR(i,100) _P("%d %d\n",X[i+1],Y[i+1]);
	
}

まとめ

最初面積を47%でなく倍の94%だと勘違いし、相当難しそうなのでわざわざ図示するコードを書いてみたら、思ったより隙間が多くてあっさり解けた。
汎用Visualizer欲しいな…。