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

問題

E: 高橋君とホテル / Tak and Hotels - AtCoder Regular Contest 060 | AtCoder

問題概要

件のホテルが一直線上に並び、座標はで与えられる。一日に移動可能な距離の上限がである。次のようなクエリが個与えられるので、各クエリに答えよ：

一日ごとにホテル間を移動する時、旅館から旅館まで移動するのに必要な日数の最小値を求めよ。

• 
• 
• 数列は昇順
• 
• 各クエリについて、旅館から旅館へ移動可能であることは保証されている

アイデア

まず、との大小関係について、からへの移動とからへの移動でかかる最小日数は同じホテルに泊まるようにすることで対称性はあるので、が常に成り立つようにしても求めるものは変わらない。

つまり、戻ることに意味が無いので移動は常に座標が増加していく方向に行うことになる。すると、あるホテルから1日で移動可能なホテルの番号の最大値(最も右にあるもの)(これをr[i]とする)を探すことはを満たす最大のということで、二分探索によって実現できる。

そうすると、あるホテルから2日で移動可能なホテルの番号の最大値はこの配列を利用すればr[r[i]]ということになる。これを入れ子にすることで日でどこまで行けるかが分かるが、このままだと遅い。そこで配列の形を変えて、r[i][j] = j番目のホテルから2^i日以内に到達可能な最も右のホテル番号として、ダブリングによって更新していく。そしてこのダブリングによって得られた配列を利用してクエリに答えていけば、各クエリに対してで答えられ、十分間に合う。クエリに答えていく部分は他の人の提出を参考にして、大きい方から見ていって越えなければ移動して次のステップを見ていくという実装が簡潔そうだった。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

// j番目のホテルから2^i日以内に到達可能な最も右のホテル番号
// 2^17 = 131072
int r[18][100000];

int main()
{
    int n,L;
    cin >>n;
    vector<int> x(n);
    rep(i,n) scanf(" %d", &x[i]);
    cin >>L;

    // ダブリング
    rep(i,n) r[0][i]=upper_bound(all(x), x[i]+L)-x.begin()-1;
    for(int i=1; i<18; ++i)rep(j,n) r[i][j]=r[i-1][r[i-1][j]];

    int Q;
    cin >>Q;
    rep(q,Q)
    {
        int a,b;
        scanf(" %d %d", &a, &b);
        --a;
        --b;
        if(a>b) swap(a,b);

        int ans=0;
        int now=a;
        for(int i=17; i>=0; --i)
        {
            if(r[i][now]<b)
            {
                now=r[i][now];
                ans+=1<<i;
            }
        }
        if(now<b)
        {
            now=r[0][now];
            ++ans;
        }

        printf("%d\n", ans);
    }

    return 0;
}