E - 高橋君とホテル

[Q] https://atcoder.jp/contests/arc060/tasks/arc060_c

・解説よくよむ
https://blog.hamayanhamayan.com/entry/2016/09/01/081201

Q. ダブリング？
A. https://algo-logic.info/doubling/
繰り返し二乗法を、開始地点別に記録するようなもの。
DP[2^k日後][i番目の町から] = 移動する町。

DP[0][0] = 0番目の町から2^0日後に到着する町。
DP[2][1] = 1番目の町から2^2日後に到着する町。
DP[10][1] = 1番目の町から2^10日後に到着する町。

のように管理する。

入力例1
9
1 3 6 13 15 18 19 29 31
10
4

ll DP[21][100010]; // DP[2^j日後][i番目の町から]=到達する町

Q. デバッグ？
A. DP[i][j]のindex値を出力。

2 3 4 6 6 6 7 8 8 
4 6 6 7 7 7 8 8 8
7 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8

DP[0][0] = 2 // 0町 の 1日後 は 2町。
DP[1][0] = 4 // 0町 の 2日後 は 4町。
DP[2][0] = 7 // 0町 の 4日後 は 7町。

Q. ダブリング入れた後は？
A. bの1日前に到達する場所を目指す。最後に1日増やす。

	  ll ans = 0;
	  
	  for(ll k=20; k>=0; --k){
		  if (DP[k][a]>=b) continue; // 1個前indexまで動く
		  a = DP[k][a]; // 町を移動する
		  ans += 1LL<<k; // 2^k日経過させる
	  }
	  ++ans;

実装。

ll DP[21][100010]; // DP[2^j日後][i番目の町から]=到達する町
ll N, L, Q;

void debug(){
	rep(i, 21){
		rep(j, N) cout << DP[i][j] << " ";
		cout << endl;
	}
}

int main(){
 cincout();
 
 cin >> N;
 vector<ll> X(N);
 rep(i, N) cin >> X[i];
 cin >> L >> Q;

 // doubling
 rep(i, N){
	  DP[0][i] = upper_bound(all(X), X[i]+L) - X.begin() - 1; // 次の町のindexを入れる
 }
 rep(k, 20){
	  rep(i, N) DP[k+1][i] = DP[k][DP[k][i]];
 }
 
//  debug();
 rep(i, Q){
	  ll a, b;
	  cin >> a >> b;
	  --a, --b;
	  if (a>b) swap(a, b);
	  ll ans = 0;
	  
	  for(ll k=20; k>=0; --k){
		  if (DP[k][a]>=b) continue; // bまであと1日でいける町を探す
		  a = DP[k][a]; // aを移動する
		  ans += 1LL<<k; // 2^k日経過させる
	  }
	  ++ans;
	  cout << ans << endl;
 }
}

https://atcoder.jp/contests/arc060/submissions/26242695