けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

TopCoder SRM 604 D1E PowerOfThree

平衡三進法!!!

問題へのリンク

問題概要

二次元座標平面上で、(0, 0) から出発して  (x, y) へと移動したい。何ステップかの移動を行うことができる。

 k ステップ目の移動では、上下左右のいずれかの方向を一つ選んで、 3^{k} だけ移動することができる (いずれかの方向に移動しなければならない)

 (x, y) へ到達することが可能かどうかを判定せよ。

制約

  • [tex -10^{9} \le x, y \le 10^{9}]

考えたこと

いわゆる、平衡三進法展開というやつ!!! 平衡三進法についてはこちら。具体的には、任意の整数を、 1, 3, 9, 27, 81, ... を高々 1 個ずつ用いて、足し引きして表すというもの。

drken1215.hatenablog.com

平衡三進法の重要な性質として、各整数  x 3^{0}, 3^{1}, 3^{2}, \dots から高々 1 個ずつ選んで足し引きして表す方法はただ一つ存在する。よって

  •  x, y を平衡三進法で表したとき
  • 同一の  k に対して
    •  x, y がともに  3^{k} を必要としたらダメ
    •  x, y がともに  3^{k} を必要としないのもダメ

ということがわかる。そうでなければ達成できる。

平衡三進法展開の方法

以下を繰り返す:

  •  x を 3 で割ったあまりが 1 なら --x、2 なら ++x する
  •  x を 3 で割る
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> PowerThree(long long n) {
    vector<int> res;
    while (n != 0) {
        int amari = (n % 3 + 3) % 3;
        if (amari == 1) res.push_back(1), --n;
        else if (amari == 2) res.push_back(-1), ++n;
        else res.push_back(0);
        n /= 3;
    }
    return res;
}

class PowerOfThree {
public:
    string ableToGet(long long x, long long y) {
        vector<int> vx = PowerThree(x);
        vector<int> vy = PowerThree(y);

        // 桁数を合わせる
        while (vx.size() < vy.size()) vx.push_back(0);
        while (vy.size() < vx.size()) vy.push_back(0);
        
        // 各桁比較
        for (int i = 0; i < vx.size(); ++i) {
            if (vx[i] == 0 && vy[i] == 0) return "Impossible";
            if (vx[i] != 0 && vy[i] != 0) return "Impossible";
        }
        return "Possible";
    }
};