SRM 507 Div2 Hard CubeRoll

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11322&rd=14436
数直線上に落とし穴があり、落とし穴の位置はholePos[i]で与えられる。最初initPosにある石をgoalPosに動かすことを考える。一回の移動で数直線上で平方数移動することができる。もし移動前と移動後の位置の間に落とし穴がある場合は石は落とし穴に落ちて終了となる。initPosからgoalPosに行く最短の移動回数を求めよ。移動できない場合は-1を返せ。

やりかた

四平方定理などから、せいぜい4以下かなというかんじ。

initPosとgoalPosの間に落とし穴が1つでもある場合は到達不可能なので-1を返す。

その上で考えられるケースは2つある。
①2つの落とし穴の間にinitPos、goalPosがあるケース
②一端のみに落とし穴があり、もう一端には落とし穴がないケース
③どちらにも落とし穴が無いケース

まず③は②と同じことである。
①の時は initPos, goalPos <= 100000 なので幅優先探索でいける。
②の時は、さらにいくつかのパターンに分けられる。
スタートとゴールの間の距離|initPos - goalPos|が

1. 平方数であるとき
2. 2つの平方数の和、もしくは差であるとき
3. 奇数であるとき
4. それ以外

(´・ω・｀)

1. これは1手で行ける
2. これは2手で行ける
3. なので任意の奇数は2手で表現できることがわかる
4. それ以外は最近傍の奇数から1手でいけるので計3手

以下ソース。修正前のコード。これでも通るけどあとで直す。コメントもつける。

class CubeRoll {
public:
  int dist[100001];
  int getMinimumSteps(int initPos, int goalPos, vector <int> holePos) {
    sort(ALL(holePos));
    int N = holePos.size();
    int l, r;
    for(int i = 0; i < N - 1; i++)
      if(holePos[i] < initPos && initPos < holePos[i + 1]){
	l = holePos[i]; r = holePos[i + 1];
	break;
      }
    if(initPos < holePos[0]) l = -INF, r = holePos[0];
    if(holePos[N - 1] < initPos) l = holePos[N - 1], r = INF;
    if(!(l < goalPos && goalPos < r)) return -1;

    cout << l << " " << r << endl;

    if(l != -INF && r != INF){
      fill(dist, dist + 100001, INF);
      queue<int> Q;
      Q.push(initPos);
      dist[initPos] = 0;
      while(!Q.empty()){
	int pos = Q.front();
	Q.pop();
	for(int i = 1; pos + i * i < r; i++){
	  int p = pos + i * i;
	  if(dist[p] > dist[pos] + 1) {
	    Q.push(p);
	    dist[p] = dist[pos] + 1;
	  }
	}
	for(int i = 1; l < pos - i * i; i++){
	  int p = pos - i * i;
	  if(dist[p] > dist[pos] + 1) {
	    Q.push(p);
	    dist[p] = dist[pos] + 1;
	  }
	}
      }
      return dist[goalPos];
    }else{
      int len = abs(goalPos - initPos);
      for(int i = 1; i * i <= 100001; i++) 
	if(len == i * i) return 1;
      if(len % 4 != 2) return 2;
      for(int i = 1; i * i <= len; i++)
	for(int j = 1; j * j <= len; j++)
	  if(len == i * i + j * j) return 2;
    }
    
    return 3;
  }
};

こんなブログでもいつのまにか1000PV行った。