kmjp's blog

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

Codeforces #238 Div2. E. Hexagons

なんだこれ。
http://codeforces.com/contest/615/problem/E

問題

2次元座標上で、点が六角グリッドの各セルを原点から渦巻き状に1マスずつたどって移動する。
(移動経路の詳細は問題文の図参照)

N手移動した後、点のいる位置を求めよ。

解法

原点の周りをグルグルまわる際、k周目は6*k個のマスを通る。
よってk周目までには(原点を除き)3*k*(k+1)個のマスを通る。

kを二分探索すると、N手目の移動後、点が何周目にいるか求められる。
Nから(k-1)周目までの通過セル数を引けば、k周目で何番目のマスに止まるか求められる。

ll N;

void go(ll a,ll b) {
	cout<<a<<" "<<b<<endl;
	exit(0);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	if(N==0) go(0,0);
	
	ll st=(1<<30)-1;
	for(i=29;i>=0;i--) {
		ll nst=st-(1<<i);
		if(N<=3*nst*(nst+1)) st=nst;
	}
	N -= 3*(st-1)*st;
	if(N<=st) go(2*st-N,2*N);
	N-=st;
	if(N<=st) go(st-2*N,2*st);
	N-=st;
	if(N<=st) go(-st-N,2*st-2*N);
	N-=st;
	if(N<=st) go(-2*st+N,-2*N);
	N-=st;
	if(N<=st) go(-st+2*N,-2*st);
	N-=st;
	return go(st+N,-2*st+2*N);
}

まとめ

C,Dより簡単だったような。