CODE FESTIVAL 2014 上海 : B - n-th Points

近い問題をGoogle Code Jamで見たな。
http://code-festival-2014-china-open.contest.atcoder.jp/tasks/code_festival_china_b

問題

２次元座標上の格子点(x,y)を以下の順で並べる。
異なる２点(x1,y1)と(x2,y2)は、以下の時(x1,y1)の方がまえに来る。(前の条件歩ｄ

1. |x1|+|y1|＜|x2|+|y2|の時。
2. |x1|+|y1|==|x2|+|y2|かつx1＜x2の時。
3. |x1|+|y1|==|x2|+|y2|かつx1=x2かつy1＜y2の時。

Q個のクエリN[i]が与えられる。
N[i]番目に来る点の座標を答えよ。

解法

1番目の条件より、各格子点は原点からのマンハッタン距離の近い順に並んでいることがわかる。
マンハッタン距離D==0な点は1つで、0より大きなDについては4*Dずつそのような点がある。
そこで二次方程式なり二分探索なりでN[i]番目の頂点のDを求めればよい。

マンハッタン距離がDである点は各X座標で(x==-D及びx==Dを除き)２個ずつあることから容易に座標を計算できる。

int Q;

ll num(ll xy) {
	if(1+2*xy*(xy+1)<xy) return 1LL<<62;
	return 1+2*xy*(xy+1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		ll V;
		cin>>V;
		
		if(V==1) {
			_P("0 0\n");
			continue;
		}
		
		ll L=0;
		for(i=29;i>=0;i--) if(V>num(L+(1<<i))) L+=1<<i;
		ll D=V-num(L)-1;
		L++;
		if(D==0) _P("%lld 0\n",-L);
		else if(D==4*L) _P("%lld 0\n",L);
		else {
			ll xx=-(L-(D+1)/2);
			ll yy=L-abs(xx);
			if(D%2==1) yy=-yy;
			_P("%lld %lld\n",xx,yy);
		}
	}
}

まとめ

ちょっと悩むけどまだまだいける。