Google Code Jam 2013 Round 1C : B. Pogo

さてB。この問題、largeの正答率が非常に低いのだけど、日本人の正答率は高かったはず…。
https://code.google.com/codejam/contest/2437488/dashboard#s=p1

問題

プレイヤーは最初２次元座標の原点におり、目的地(X,Y)が与えられる。
プレイヤーはAターン目には東西南北のいずれかに距離Aだけ移動できる。
500ターン以内で、目的地に到達する移動手順を答えよ。

解法

これ、どこかで見たと思ったらAutumn Fest Eと非常に近い。
よって、Editorialを見て実装するだけ。

まず、目的地に到達する最小ターン数Tを数える。
Tは以下の２つを満たせばよい。Tは500以下なので、1ずつ増やしてもすぐ見つかる。

• 
• 

次に移動方向は、1ターン目からでなくTターン目から逆順で求める。
目的地までのX軸方向とY軸方向のうち、距離が遠い側の軸を近づける方向に求めればよい。

char str[1000002];
void solve(int _loop) {
	int i,j,x,y,ne=0;
	
	x=GETi();
	y=GETi();
	int t=0,ts=0;
	for(t=0;;t++) {
		ts+=t;
		if(ts%2==(abs(x)+abs(y))%2 && ts>=(abs(x)+abs(y))) break;
	}
	
	ZERO(str);
	while(t) {
		if(abs(x)>=abs(y)) {
			if(x>0) {
				str[t]='E';
				x-=t;
			}
			else {
				str[t]='W';
				x+=t;
			}
		}
		else {
			if(y>0) {
				str[t]='N';
				y-=t;
			}
			else {
				str[t]='S';
				y+=t;
			}
		}
		t--;
	}
	
	_PE("Case #%d: %s\n",_loop,str+1);
}

まとめ

Autumn Fest Eを知ってればラクだけど、知らないと厳しいな。
まぁAL・Bs・CsでRound2進出できるからいいんだけど…。