問題
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; } }