KUPC2014 : H - 自転車走

解いたのだいぶ前なのになんで書いてないんだろう。
http://kupc2014.contest.atcoder.jp/tasks/kupc2014_h

問題

初期位置から距離L離れた場所まで自転車で走るゲームを行う。
このゲームでは、初期位置からの距離が[A[i],B[i]]の区間がN個与えられており、この間は走行可能である。

このままでは走行不可能な区間があるが、そこでジャンプを用いてそのような区間を抜けることを考える。
1回ジャンプすると、現在位置からW先の地点に移動できる。
その間移動不可能な地点が含まれていても良い。
ただしジャンプ前後の位置はともに走行可能でなければならない。

目的地に着くまで必要な最小ジャンプ回数を求めよ。

解法

この問題ではまず前提として、各地点に到着する最小ジャンプ回数は(到達可能であれば)単調増加である。
各地点について、到着可能な範囲と、そこに至る最小ジャンプ回数を求めよう。

i番目の地点につくには、[A[i]-W,B[i]-W]の区間に含まれるような以前の到着可能な地点からジャンプすればよい。
そのような地点は複数あり得るが、左記の単調増加の考察により、[A[i]-W,B[i]-W]に含まれるもっとも初期位置に近い到達可能な位置からジャンプすればよいことがわかる。
よって尺取法の要領でそのような位置を更新していこう。

int N,L,W;
int A[100001],B[100001];
int F[100001],DP[100001];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>L>>W;
	
	FOR(i,N) {
		cin>>A[i]>>B[i];
		F[i]=B[i];
		DP[i]=1000000;
	}
	F[0]=DP[0]=x=0;
	for(i=1;i<N;i++) {
		while(x<i && (B[x]<A[i]-W || DP[x]>=1000000)) x++;
		if(x==i || F[x]+W>B[i]) continue;
		F[i]=max(A[i],F[x]+W);
		DP[i]=DP[x]+1;
	}
	
	if(DP[N-1]>=1000000) DP[N-1]=-1;
	cout << DP[N-1] << endl;
}

まとめ

1年以上前のコードだけど、このぐらい短いと何やってるかなんとか読み解けるな…。