はまやんはまやんはまやん

hamayanhamayan's blog

高橋くんとホテル / Tak and Hotels [ARC 060 : E]

問題

http://arc060.contest.atcoder.jp/tasks/arc060_c

N軒のホテルがある。
i軒目のホテルはx[i]の位置にある。
以下の条件を満たして移動する。

  • 1日の移動距離はL以下
  • 1日の終わりには必ずホテルにいる

この時、Q個の以下のクエリが与えられる。
a[i]番目のホテルからb[i]番目のホテルに移動するのにかかる最短日数を出力せよ。

2 <= N <= 10^5
1 <= L <= 10^9
1 <= Q <= 10^5

帰納的考察(解説とkmjpさんのブログ見た)

1. クエリ問題なので、前計算をするのだろう
2. 全ての答えを用意しておくのは難しいな
3. うーん

――壁――

4. 「a->bとb->aの最短日数は同じ」
5. 以下の様なものを考える

dp[i][j] = i番目のホテルから2^j日間で到達できる最右端のホテル
dp[i][j + 1] = dp[dp[i][j]][j]

6. 漸化式がダブリングの要領で作られる
7. (こんな発想どこからやってくるんだろうか)
8. あとはこれを使って答えを計算していく
9. 具体的には 2^20日かけて移動、2^19日かけて移動、…を順番に行っていく

実装

http://arc060.contest.atcoder.jp/submissions/861010

#define rrep(i,a,b) for(int i=a;i>=b;i--)
int N;
int X[101010];
int L, Q;
int dp[101010][21];
//-----------------------------------------------------------------
int main() {
	cin >> N;
	rep(i, 0, N) scanf("%d", &X[i]);
	cin >> L >> Q;

	rep(i, 0, N) dp[i][0] = upper_bound(X, X + N, X[i] + L) - X - 1;
	rep(i, 0, 20) rep(j, 0, N) dp[j][i + 1] = dp[dp[j][i]][i];

	rep(q, 0, Q) {
		int a, b;
		cin >> a >> b;
		if (a > b) swap(a, b);
		a--; b--;

		int ans = 0;
		rrep(i, 20, 0) if (dp[a][i] < b) {
			a = dp[a][i];
			ans += 1 << i;
		}
		ans++;
		cout << ans << endl;
	}
}