TopCoder SRM 507 Div2 Hard CubeRoll

知らなかった知見を得られた問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11322

問題

1次元の数直線上に箱がある。
箱を初期位置からゴールまで移動したい。
この時、1ターンで任意の平方数だけ移動できる。
ただし、数直線にはいくつか穴があり、移動中そこを通ることはできない。

最小で何ターンでゴールにたどり着けるか。

解法

初期位置とゴールの間に穴がある場合は、ゴールできない。

初期位置とゴールがともに挟まれている場合、ダイクストラの要領で最短ターン数を求めればよい。
穴の間の距離は高々100000であり、1ターンの移動経路は高々223通り(√50000 * 2)なので、総当たりでも間に合う。

ゴールが初期位置の左にある場合、初期位置の左またはゴールの右に穴がない場合は事情が異なる。
この場合、10000^2右に行って9999^2左に戻る、というように非常に大きな範囲の座標を行き来できるので、DPで解くことはできない。

なお、初期位置に左に穴がない場合は左移動を先に行って右移動を後、ゴールの右に穴がない場合は右移動を先に行って左移動を後に行えばよいので、どちらに穴がない場合も同じように考えることができる。

ではDPできないのでどうするか。

• 初期状態の距離が平方数なら1手確定。
• 以下の条件では2手で行ける。
  • 初期状態の距離が奇数
  • 初期状態の距離が4の倍数
  • 初期状態の距離が平方数の和
• それ以外の時は3手。

1手は良いとして、2手で行ける条件を示す。
x^2右に行ってy^2左に戻ると、移動距離は(x^2-y^2)=(x+y)(x-y)である。

• 距離が奇数(2K+1)なら、x=K+1、y=Kとすると(x^2-y-2)=2K+1にできる。
• 距離が4の倍数(4K)なら、x=K+1、y=K-1とすると(x^2-y-2)=4Kにできる。

なお、距離が4の倍数でなく偶数の場合、x^2-y^2で実現することはできない。
x,yが偶数・奇数ならその２乗は４の倍数か４で割って１余るので、そのような数を２つ足しても４で割って２余る数にはならない。
ただし、４で割って１余る数を２つ足すと４で割って２余るので、x^2+y^2の形で到達できる場合もある。
題意よりx^2+y^2<=100000なので、この範囲なら総当たりで判定できる。

最後に距離が４の倍数でなく２の倍数で、かつ平方数の和で表せない場合、１手目で１歩動けば残り距離が奇数になるのであと２手でゴールできる。

int cost[100001];
class CubeRoll {
	public:
	
	int type1(int diff) {
		int sq=sqrt(diff+0.5);
		if(sq*sq==diff) return 1;
		if(diff%4==0) return 2;
		if(diff%2==1) return 2;
		for(int x=1;x*x<diff;x++) {
			int y=sqrt(diff-x*x+0.5);
			if(x*x+y*y==diff) return 2;
		}
		return 3;
		
	}
	int type2(int st,int go,int rh) {
		int i;
		FOR(i,rh) cost[i]=1<<29;
		cost[st]=0;
		queue<int> Q;
		Q.push(st);
		while(!Q.empty()) {
			st=Q.front();
			Q.pop();
			for(i=1;i*i<=rh;i++) {
				if(st+i*i<rh && cost[st+i*i]>cost[st]+1) cost[st+i*i] = cost[st]+1,Q.push(st+i*i);
				if(st-i*i>=1 && cost[st-i*i]>cost[st]+1) cost[st-i*i] = cost[st]+1,Q.push(st-i*i);
			}
		}
		return cost[go];
	}
	
	int getMinimumSteps(int initPos, int goalPos, vector <int> holePos) {
		int lh=-1<<30,rh=1<<30;
		ITR(it,holePos) {
			if((*it-initPos)*(ll)(*it-goalPos)<0) return -1;
			if(*it<initPos) lh=max(lh,*it);
			if(*it>goalPos) rh=min(rh,*it);
		}
		if(lh<0 || rh>=1<<30) return type1(abs(initPos-goalPos));
		else return type2(initPos-lh,goalPos-lh,rh-lh);
	}
};

まとめ

任意の整数は３つの平方数の加減算で表現できる、という特性を初めて知った。