AtCoder ARC #060 : E - 高橋君とホテル / Tak and Hotels

これはすんなり思いつけたね。
http://arc060.contest.atcoder.jp/tasks/arc060_c

問題

N個の拠点が座標X[i]にある。Xは昇順に並んでいる。
隣接する拠点同士の距離はL以下であることが保証される。

以下のクエリQ個に答えよ。
２つの拠点の対(a,b)が与えられる。
１回のジャンプで距離L以内の拠点に移動できる場合、aからbに最小何回のジャンプで移動できるか。

解法

各クエリはa＞bの場合a,bを逆にしても良いので、以後a＜bの場合を考える。

ダブリング＋二分探索で解く。
まず1回のジャンプで最大何手後ろの拠点まで移動できるか、lower_bound等で求める。
あとはダブリングで2^n回のジャンプでどこまで移動できるか求められる。

各クエリに対し、このダブリングの結果を用いて二分探索し、最小何手でaからbに移動できるかを求める。

int N;
int L;
int Q;
int X[101010];
int ne[101010][20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i];
	cin>>L;
	
	FOR(i,N) ne[i][0]=lower_bound(X+i,X+N,X[i]+L+1)-1-X;
	FOR(i,19) {
		FOR(x,N) ne[x][i+1]=ne[ne[x][i]][i];
	}
	
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		x--,y--;
		if(x>y) swap(x,y);
		
		int day=0;
		for(i=19;i>=0;i--) if(ne[x][i]<y) {
			x=ne[x][i];
			day+=1<<i;
		}
		
		cout<<day+1<<endl;
	}
}

まとめ

Dを解いてたらEがポツポツ解かれだしたけど、この難易度なら納得。