平衡三進法!!!
問題概要
二次元座標平面上で、(0, 0) から出発して へと移動したい。何ステップかの移動を行うことができる。
ステップ目の移動では、上下左右のいずれかの方向を一つ選んで、 だけ移動することができる (いずれかの方向に移動しなければならない)
へ到達することが可能かどうかを判定せよ。
制約
- [tex -10^{9} \le x, y \le 10^{9}]
考えたこと
いわゆる、平衡三進法展開というやつ!!! 平衡三進法についてはこちら。具体的には、任意の整数を、 を高々 1 個ずつ用いて、足し引きして表すというもの。
平衡三進法の重要な性質として、各整数 を から高々 1 個ずつ選んで足し引きして表す方法はただ一つ存在する。よって
- を平衡三進法で表したとき
- 同一の に対して
- がともに を必要としたらダメ
- がともに を必要としないのもダメ
ということがわかる。そうでなければ達成できる。
平衡三進法展開の方法
以下を繰り返す:
- を 3 で割ったあまりが 1 なら --x、2 なら ++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"; } };