ARC060 E - 高橋君とホテル

問題のリンク

E - Tak and Hotels

考察

1 日でいけるところまでいく、を繰り返すのが最善。x[i] から1 日でいける最も右にあるホテルの位置は、二分探索で簡単に求まる。

サンプル1 はこんな感じになる。（0 - indexed）

クエリ1 個目のホテル0 からホテル7 まで行くときにかかる日数は、このグラフをみるとすぐ4 とわかる。あとはこのクエリを高速に処理することを考える。

なんかダブリングが使えそう
全ての頂点の辺の出次数が1 であるようなグラフはダブリングが使えそうなイメージ。

c[i][k] := 頂点i から 回辺を辿ってたどり着く頂点のindex 。 とする。

頂点i から頂点j に行くときにかかる日数を求める場合、答え= 0 と初期化しておいて、
1. c[i][k] をk の昇順に見ていき、c[i][k] がj 未満である最大のk 見つける。このとき、k が0 であれば、答えに1 を足して終了する。
2. 頂点i から回辺を辿って頂点c[i][k] まで進む。このとき答えに を足す。
3. 頂点i を新たにi = c[i][k] として1 に戻る。

これで多分、O(log(N)) で答えを求められるのかな→　通った、いけてた。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
int main()
{
  int n; cin >> n;
  vector<int> x(n);
  rep(i,n) cin >> x[i];
  int l; cin >> l;
  int q; cin >> q;
  vector<int> a(q), b(q);
  rep(i,q) {
    cin >> a[i] >> b[i];
    a[i]--; b[i]--;
  }

  int M = 20;
  vector<vector<int>> c(n, vector<int>(M));
  rep(i,n) {
    int lb = -1, ub = n;
    while(ub - lb > 1) {
      int mid = (ub + lb)/2;
      (x[mid] <= x[i] + l ? lb : ub) = mid;
    }
    c[i][0] = lb;
  }

  // ダブリングテーブル作成
  rep1(j,M-1) {
    rep(i,n) {
      c[i][j] = c[c[i][j-1]][j-1];
    }
  }

  vector<int> pow2(M+1);
  pow2[0] = 1;
  rep(i,M) {
    pow2[i+1] = pow2[i] * 2;
  }
  
  rep(i,q) {
    if(a[i] > b[i]) swap(a[i], b[i]);
    int res = 0;
    int v = a[i];
    while(1) {
      int idx = 0;
      while(c[v][idx] < b[i]) idx++;
      if(idx == 0) {
    res += pow2[idx];
    break;
      }
      else {
    res += pow2[idx-1];
      }
      v = c[v][idx-1];
    }
    cout << res << "\n";
  }
  
  return 0;
}