TopCoder SRM 475 Div 2 Hard RabbitJumping

む、難しい……

問題概要

ウサギが数直線の原点にいる。
ここから幅2の小ジャンプまたは幅longJumpの大ジャンプを繰り返して1,000,000,001の点に到達したい。
数直線上には穴があり、i番の穴は、区間[holes[i*2],holes[i*2+1]]で与えられる(両端含む)

このとき、ゴールまで辿り着くために必要な大ジャンプの最小回数を求めよ。
ゴールへ辿り着くことができない場合-1を返せ。


3≦longJump≦1,000,000,000
0≦holes[i]≦1,000,000,000を満たし、holesの要素は50以下であるものとする。

解法

数直線上を落とし穴で区切られた区間に分割することを考える。
(-∞,holes[0]]-1], [holes[0]+1,holes[1]-1], ... , holes[n-1]+1,∞)という具合に。


そうすると、各区間が行き来できるかどうかを辺の有無に対応させたグラフを考えることができて、それでワーシャルフロイドをやれば良いような気がする。


小ジャンプの幅が1ならそれでよい。
しかし、小ジャンプの幅が2なので、ある区間に小ジャンプで到達して、その区間内で(コストのかからない)小ジャンプのみで偶奇の違う点に行くことはできない。


そこで、1つの区間を偶数と奇数で分割するようにすれば良い。
(ある区間の偶数に到達できればその区間の偶数は全て小ジャンプで到達できる。奇数も同様)

ソースコード

typedef pair<long,long> pll;

int n,m;
int e[150][150];
pll itvl[150];

bool IS(ll a,ll b,ll c,ll d)
{
	return a<=c&&c<=b||a<=d&&d<=b||
	c<=a&&a<=d||c<=b&&b<=d;
}
bool intersect(pll iv1,pll iv2,int jmp)
{
	ll a=iv1.first,b=iv1.second;
	ll c=iv2.first,d=iv2.second;
	if((a+jmp)%2!=c%2)return 0;
	
	return IS(a+jmp,b+jmp,c,d)||IS(a,b,c+jmp,d+jmp);
}

class RabbitJumping {
	public:
	int getMinimum(vector <int> holes, int largeJump) 
	{
		vector<ll> H;
		H.pb(-inf); rep(i,holes.size())H.pb(holes[i]); H.pb(inf);
		
		m=0; n=H.size()/2;
		rep(i,n)
		{
			itvl[m]=mp(H[i*2]+1,H[i*2+1]-1);
			if(itvl[m].first%2)itvl[m].first++;
			if(itvl[m].second%2)itvl[m].second--;
			if(itvl[m].first<=itvl[m].second)m++;
			
			itvl[m]=mp(H[i*2]+1,H[i*2+1]-1);
			if(itvl[m].first%2==0)itvl[m].first++;
			if(itvl[m].second%2==0)itvl[m].second--;
			if(itvl[m].first<=itvl[m].second)m++;
		}
		itvl[m++]=mp(1000000001,1000000001);
		
		rep(i,m)rep(j,m)e[i][j]=1<<28;
		rep(i,m)rep(j,m)
		{
			if(intersect(itvl[i],itvl[j],largeJump))e[i][j]=e[j][i]=1;
			if(intersect(itvl[i],itvl[j],2))e[i][j]=e[j][i]=0;
		}
		rep(k,m)rep(i,m)rep(j,m)e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
		
		return e[0][m-1]==1<<28?-1:e[0][m-1];
	}
};