TopCoder SRM 604 Div1 Easy PowerOfThree

SRM604に参加。Mediumはさっくり解けたと思ったらまんまと罠にはまって落とした。
ただ、他に人もSubmit中正答率1/9だったのと、Challenge１つ取ったおかげで結構いい順位。
http://community.topcoder.com/stat?c=problem_statement&pm=12917

問題

２次元座標において、原点から(x,y)に移動したい。
k手目の移動では、上下左右のいずれかの方向に3^kだけ移動できる/しなければならない。
(x,y)に到達できるか答えよ。

解答

(x,y)の正負はどちらでも、上下・左右移動をひっくり返せば同じなので、(x,y)が正の場合を考える。
x,yを３進数表記したとき、各k手目について、xかyのいずれか片方だけが下からk桁目が非0であれば、3^kの増減によりその桁を0に出来る。

よって、下の桁から移動方法を決めていけばよく、x,yが共に0になるまで以下の処理を繰り返せばよい。

• x==0,y==0なら到達可能で終了。
• x,yがともに３の倍数なら到達不可。どちらを移動させても後でその桁が余る。
• x,yがともに３の倍数でないなら到達不可。どちらか片方はその桁が余ってしまう。
• x,yのうち３の倍数でない方について、３で割った余りが1なら1引き、2なら1足す。
• x,yは3の倍数になっているはずなのでともに3で割る。

class PowerOfThree {
	public:
	string ableToGet(int x, int y) {
		ll X=abs(x),Y=abs(y);
		for(ll r=1;r<20000000000LL;r*=3) {
			if(X==0&&Y==0) return "Possible";
			if((X%3)&&(Y%3)) return "Impossible";
			if(((X%3)==0)&&((Y%3)==0)) return "Impossible";
			
			else if((X%3)==1) X-=1;
			else if((X%3)==2) X+=1;
			else if((Y%3)==1) Y-=1;
			else if((Y%3)==2) Y+=1;
			X/=3;
			Y/=3;
			X=abs(X);
			Y=abs(Y);
		}
		return "Impossible";
	}
};

なお、Div2 Easyは上と右にしか移動できないようにした問題となっている。
こちらは、途中３で割って２余るケース（つまり上か右に移動して次に下か左に戻る必要がある）が到達不可になる。

class PowerOfThreeEasy {
	public:
	string ableToGet(int x, int y) {
		ll X=abs(x),Y=abs(y);
		
		for(ll r=1;r<20000000000LL;r*=3) {
			if(X==0&&Y==0) return "Possible";
			if((X%3)&&(Y%3)) return "Impossible";
			if(((X%3)==0)&&((Y%3)==0)) return "Impossible";
			else if((X%3)==1) X-=1;
			else if((X%3)==2) return "Impossible";
			else if((Y%3)==1) Y-=1;
			else if((Y%3)==2) return "Impossible";
			X/=3;
			Y/=3;
			if(X==0&&Y==0) return "Possible";
		}
		return "Impossible";
	}
};

まとめ

これはすんなり思いついてよかった。
ただ、x,yは高々3^19なので、上下と左右どちらに移動するかを2^19通りbitDPでも余裕で間に合ったようだ。