TopCoder SRM 604 Div1 Easy PowerOfThree [1人競技プログラミング Advent Calendar 2016 5日目]

この記事は1人競技プログラミング Advent Calendar 2016 5日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement

ロボットが初期座標(0,0)に存在する。
このロボットを座標(x,y) (-1,000,000,000 <= x,y <= 1,000,000,000)に移動させたい。
ロボットはkステップ目(0から)には、3^k分上下左右の何方かに移動することが出来る。 つまり、1,3,9,27…と移動することが出来る量が変化していく。どのステップでも必ず上下左右の何処かには移動しなければならない。
xとyが与えられた際に、このロボットが目的地まで辿り着けるかどうかを判定せよ。

解いた方法：
ゴールに辿り着けるかという問題を考えると非常に難しいので、逆にゴールから目的地に辿り着けるかという問題を考える。
このゲームでは、x座標でもy座標でも必ずスタート地点から遠い方を優先して動かさなければならない。
sum(3⁰..3^k-1) より 3^kの方が大きくなる為、距離が遠い方を動かさないと後々必ずステップ数が足りなくなる。(もしくはそもそもスタート地点に辿り着けない)
ロボットが移動するステップ数は一意に求めることができ、(x=0,y=0を除いて)3^k - sum(3⁰..3^k-1) <= max(abs(x), abs(y)) <= sum(3⁰..3^k)を満たすkがステップ数となる。
後は上記の手法を使い、座標(x,y)からkステップを逆に辿っていき座標(0,0)に戻る事が出来たかどうかで求めることができる。

この手の問題の逆から考えるをすっかり頭から抜けてて解くのに時間掛けたり、最初のmax_num = max(abs(x), abs(y))でabsを付け忘れて1WAを出してしまった…。反省。

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

LL create_3k(int k){
    LL res = 1;
    REP(i, k) res *= 3;
    return res;
}

class PowerOfThree {
    public:
    LL x;
    LL y;
    string ableToGet(int _xxx, int _yyy) {
        x = _xxx, y = _yyy;

        LL max_num = max(abs(x), abs(y));
        LL tmp = 0;
        int k = 0;
        while(true){
            if(max_num <= tmp) break;
            k++;
            tmp += create_3k(k-1);
        }

        while(k != 0){
            if(abs(x) < abs(y)) swap(x, y);
            k--;
            if(x < 0){
                x += create_3k(k);
            }else{
                x -= create_3k(k);
            }
        }

        return (x==0 && y==0) ? "Possible" : "Impossible";
    }
};