SRM 475 Div2 Hard RabbitJumping

問題

うさぎが数直線上でx=0の位置からジャンプを始めて、ゴール地点のx=1000000001に行こうとしている。うさぎは2種類のジャンプが出来、一回のジャンプで(x - 2)か(x + 2)に移動できるスモールジャンプと、(x - largeJump)か(x + largeJump)に移動できるラージジャンプがある。数直線上には落とし穴があり、holes[2 * i]～holes[2 * i + 1]間が落とし穴になっている。うさぎが落とし穴に落ちないようにゴールに行くとき、もっとも少なくてすむラージジャンプの回数を求めよ。ゴールに到達不能なら-1を返せ。

やりかた

幅優先探索などではTLEしてしまう。そこで、区間の偶奇に着目する。

まずlargeJumpが偶数の場合、奇数点であるゴール地点にはたどり着けないので-1。
移動できる区間は落とし穴区間によって区切られた区間である。ラージジャンプによって、ある移動可能区間iからある区間j(>= i)に移動できるとき、
①iの偶数地点からjの奇数地点に移動できるか（かつその逆の移動）
②iの奇数地点からjの偶数地点に移動できるか（かつその逆の移動）
を調べる。移動できるようなら、それはラージジャンプ一回なのでコスト1で移動できる。このようにある区間からある区間への移動について偶奇に分けて考える。
スモールジャンプについては区間をまたぐことが出来ないので同区間の
①偶数地点から偶数地点に移動できるか（かつその逆の移動）
②奇数地点から奇数地点に移動できるか（かつその逆の移動）
を調べる。移動できるようなら、それはスモールジャンプ一回なのでコスト0で移動できる。

このようにすればある区間の偶奇についてを一つのノードとした最短経路問題となるので適当な方法で答えを求めることができる。

以下ソース。

ll dist[110][110];

class RabbitJumping {
public:
  int getMinimum(vector <int> holes, int largeJump) {
    if(largeJump % 2 == 0) return -1; 
    for(int i = 0; i < 110; i++) fill(dist[i], dist[i] + 110, INF);
    int N = holes.size() / 2;

    //移動できる区間に直す
    vector<pair<ll, ll> > seg;
    for(int i = 0; i <= N; i++){
      if(i == 0) seg.push_back(make_pair(-INF, holes[0] - 1));
      else if(i == N) seg.push_back(make_pair(holes[2 * (N - 1) + 1] + 1, INF));
      else{
	if(holes[2 * (i - 1) + 1] + 1 <= holes[2 * i] - 1)
	  seg.push_back(make_pair(holes[2 * (i - 1) + 1] + 1, holes[2 * i] - 1));      
      }
    }

    N = seg.size();

    //largeJump による奇遇の変化
    for(int i = 0; i < N; i++){
      for(int j = i; j < N; j++){
	ll mind = seg[j].first - seg[i].second;
	ll maxd = seg[j].second - seg[i].first;
	if(mind < largeJump && largeJump < maxd){
	  dist[2 * i][2 * j + 1] = dist[2 * j + 1][2 * i] = 1;
	  dist[2 * i + 1][2 * j] = dist[2 * j][2 * i + 1] = 1;
	}

        //largeJumpにより左区間の右端から右区間の左端までをやっとまたげる
	if(largeJump == mind){
	  dist[2 * i + (seg[i].second) % 2][2 * j + (seg[i].second + 1) % 2] = 1;
	  dist[2 * j + (seg[i].second + 1) % 2][2 * i + (seg[i].second) % 2] = 1;
	}

        //largeJumpにより左区間の左端から右区間の右端まで一気に移動してしまう
	if(largeJump == maxd){
	  dist[2 * i + (seg[i].first) % 2][2 * j + (seg[i].first + 1) % 2] = 1;
	  dist[2 * j + (seg[i].first + 1) % 2][2 * i + (seg[i].first) % 2] = 1;
	}
      }
    }

    //smallJump による奇遇の移動
    for(int i = 0; i < N; i++){
      ll width = seg[i].second - seg[i].first;
      if(width == 2){
	dist[2 * i + (seg[i].first) % 2][2 * i + (seg[i].first) % 2] = 0;
      }
      if(width > 2){
	dist[2 * i][2 * i] = 0;
	dist[2 * i + 1][2 * i + 1] = 0;
      }
    }

    for(int k = 0; k < 2 * N; k++)
    for(int i = 0; i < 2 * N; i++)
    for(int j = 0; j < 2 * N; j++)
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    return dist[0][2 * (N - 1) + 1] >= INF ? -1 : dist[0][2 * (N - 1) + 1];
  }
};