読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

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

問題

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

問題概要

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

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

  •  2 \le n \le 10^5
  •  1 \le x_i \le 10^9
  • 数列 xは昇順
  •  1 \le Q \le 10^5
  • 各クエリについて、旅館aから旅館bへ移動可能であることは保証されている

イデア

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

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

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

実装(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;
}