概要
二次元平面上の座標 ( 0, 0 ) にロボットがいる。このロボットは複数回の移動が可能であり、k 回目（ 0-based ) の移動では上下左右のいずれかの方向に距離 移動する。座標 ( x, y ) に移動することができるかどうか求めよ。
解法
まず、 について、次式が成り立ちます。*1
証明のために左辺の総和 s を求めます。
辺々 3 を乗じて、
この式から元の式を引くと
よって
この関係を度々使います。*2
では本題に入りましょう。t 回の移動で目標地点に行けると仮定したとき、移動を逆順にして ( x, y ) から原点を目指すと考えることができます。今原点ではないある座標にいて、次の移動でどちらに移動するべきか考えます。先程の式から分かるように、一度原点から遠ざかる方向（絶対値が増える方向）に移動してしまうとその移動分を取り返せないので、それ以上原点に近づくことができなくなることが分かります。従って、取れる選択はどちらの座標を原点に近づけるか、です。原点を始点に考えると、常に原点からのマンハッタン距離が大きくなるように移動することが分かります。
（原点を始点とした）ある段階での移動では、先程の式より、今までの移動距離の合計の 2 倍（とちょっと）の距離を移動します。従って、この移動が完了したとき、対象となった座標の絶対値は必ず他方のそれより大きくなっています。逆順で考えると、直前に移動があったのは絶対値が大きい方の座標であることが分かります。以上をまとめると、t を仮定したときの最適な手順は逆方向から座標の絶対値が大きい方を原点に近づけ続けることであると分かります。
解候補となる t を全て試せば問題が解けますが、t の上界はいくつになるでしょうか？ 適当な数 20 を 3 の肩に乗っけて計算すると、 となります。ところで、
の無限級数が
に収束するので
で 2 倍を超えているので、t の上界は 20 ということになります *4。この範囲ならば全通り試すことができるので、各 t に対して先程の手順を適用し、最終的に ( 0, 0 ) にできるものを探せます。
コード
typedef long long LL; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) class PowerOfThree { public: vector<LL> moves; string ableToGet( int x, int y ) { moves.clear(); moves.resize( 30 ); moves[0] = 1; REP( i, 1, moves.size() ) { moves[i] = moves[ i - 1 ] * 3; } REP( i, -1, 26 ) { if ( ok( abs( x ), abs( y ), i ) ) { return "Possible"; } } return "Impossible"; } bool ok( LL x, LL y, const int turn ) { for ( int t = turn; 0 <= t; t-- ) { LL &target = x < y ? y : x; target = abs( target - moves[t] ); } return x == 0 && y == 0; } };
