Google Code Jam 2020 Round 1B : A. Expogo

Round1Aより難しく感じた。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2/00000000002d5b62

問題

2次元座標上を(0,0)から(X,Y)に移動したい。
iステップ目の移動では、上下左右いずれかにちょうど2^(i-1)だけ移動できる。
(X,Y)に到達する手段が存在するなら、それを答えよ。

解法

現在位置から目的地までの相対的な位置を(X',Y')とする。
まだ目的地についておらず、次にiステップ目を取るなら、2進数表記でX'とY'のどちらか片方が2^(i-1)のbitが立っていなければならない。
その場合、立っているbitを2^(i-1)を足すか引くかを総当たりしよう。

string hoge(int X,int Y) {
	if(abs(X)+abs(Y)==1) {
		if(X==1) return "E";
		if(X==-1) return "W";
		if(Y==1) return "N";
		if(Y==-1) return "S";
	}
	if(X==0 && Y==0) return "";
	if(abs(X)%2==0 && abs(Y)%2==1) {
		string s=hoge(X/2,(Y+1)/2);
		if(s!="IMPOSSIBLE") return "S"+s;
		s=hoge(X/2,(Y-1)/2);
		if(s!="IMPOSSIBLE") return "N"+s;
	}
	if(abs(X)%2==1 && abs(Y)%2==0) {
		string s=hoge((X+1)/2,Y/2);
		if(s!="IMPOSSIBLE") return "W"+s;
		s=hoge((X-1)/2,Y/2);
		if(s!="IMPOSSIBLE") return "E"+s;
	}
	return "IMPOSSIBLE";
	
	
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	int X,Y;
	cin>>X>>Y;
	string S=hoge(X,Y);
	_P("Case #%d: %s\n",_loop,S.c_str());
}

まとめ

AtCoderでも似たようなの見たね。