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

「3月中に毎日1問解いて黄色になろう！」キャンペーン8問目。AtCoder700点埋めを始めました。

問題概要

N個の町が一直線に並んでおり、左からx[i]の座標にある。一日にその町から距離L以内の町にしか移動できない時、Q個のクエリa_i、b_iに対して、a_iからb_iへ移動するには最短何日かかるか答えよ。
N,Q≦10⁵

解説

まず最初に、クエリが有向か無向か考えます。a→bであるルートがあれば、それと全く逆向きで通ればb→aになるので、無向です。このことより、各クエリに対して、a<bとして良いです。

全部のクエリにシミュレーションで対応していると、O(NQ)位かかって普通に間に合いません。ところで、適当な区間を何日で通れるか記録しておくと計算が速くなりますね？

ってことで平方分割もしくはダブリングします。自分はダブリングを選びました。a<bなので、座標が大きくなる方向のみを考えるといいです。

pos[i][j]:地点iから2^j日でどこまで行けるか
とします。必ず隣の町には行ける設定なので、適当に2²⁰日後位まで求めるんですが、最初の1日だけ各地点からどこまでいけるのかを求めたら、2ⁱ日後について、
pos[from][i]=pos[pos[from][i-1]][i-1]
とすることで、各地点でボトムアップに2ⁱ日後にどこまで行けるかを求めることが出来ます。

ところで、最初の1日の計算自体も下手にやるとO(N²)で死にます。これはしゃくとり法っぽく「pos[0][0]≦pos[1][0]≦pos[2][0]≦...≦pos[N-1][0]=N-1」という性質を利用するとO(N)で求められます（コードを見た方が速い気がしますが、分からなかったらしゃくとり法をググってください）

で、肝心のクエリに対しては、a<bの間aからbを超えない範囲で前進することを繰り返すので、クエリ一つにつきO((logN)²)だと思います。答えの上限がNなので。
ということで全体ではO(Q(logN)²)でした。

https://beta.atcoder.jp/contests/arc060/submissions/2243083

int main() {
    int n; cin >> n;
    vector<ll> x(n);
    rep(i, n)   cin >> x[i];
    int l; cin >> l;
    vector<vint> to(n, vint(20));
    rep(i, n)   to[i][0] = i;
    int tox = 0;
    while (tox + 1 < n && x[tox + 1] - x[0] <= l)    tox++;
    to[0][1] = tox;
    srep(i, 1, n) {
        while (tox + 1 < n && x[tox + 1] - x[i] <= l) tox++;
        to[i][1] = tox;
    }
    srep(i, 2, 20)    rep(j, n) {
        to[j][i] = to[to[j][i - 1]][i - 1];
    }
    int q; cin >> q;
    while (q--) {
        int a, b;  cin >> a >> b;
        a--;    b--;
        if (a > b) swap(a, b);
        int ret = 0;
        while (a < b) {
            int add = 1;
            int days = 1;
            while (to[a][days + 1] < b) {
                days++;
                add *= 2;
            }
            ret += add;
            a = to[a][days];
        }
        cout << ret << endl;
    }
    return 0;
}

感想

難易度は最近の700点問題と比べるとかなり簡単？に感じました。
やっぱり少し難易度が上がるとC++ばっかりで解いてしまうので、PythonとかRubyで縛ってもいいのかな…と思ってしまいます。