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

問題

arc060.contest.atcoder.jp

考察

やることはとてもシンプルで、いかに高速化するかという問題のようです。

部分点解法

クエリ毎にaからbへ実際に移動してみれば、 O(N * Q)で間に合います。

満点解法

まず、距離の短い点が多くてもTLEしないようにしてみましょう。
これは、 x[a + L] で行ける最大の点を二分探索で探せば、Lで行けるギリギリの点を logNで見つけられるため達成できます。
また、各点に対してこの値を保持することで、再度計算せずに済み全体で高速化されます。

距離の長い点が沢山ある場合はどうすればよいのでしょうか。
ここで、上で求めた値を発展させた以下のようなデータを保持することを考えます。

dp[i][j] := i番目の点から 2^{j}回の移動で到達できる最大の点のインデックス

この配列は、サイズが N * logNで、以下の様な漸化式で簡単に埋めることができます。
j-1はjの半分を表すので、2回繰り返せば良いですね。

 dp[i][j] := dp[ dp[i][j-1] ][j-1]

この配列を使うと、T回の移動で点bより先にたどり着けるかが分かります。
実際の処理としては、Tを2進数で表して上位ビットから見てゆき、立っていれば移動をすればよいです。
Tは高々Nなので、クエリ毎に二分探索をしてTを決め打ちし、 O(Q*logN * logN) となり間に合います。

工夫

 a > bのクエリが与えられた場合、各xに-1を掛けて処理すると、どのクエリでも左から右へ処理することになり(それなりに)綺麗に書けました。

コード

int main() {
    int N;
    cin >> N;

    // 右から左に行く場合は、-にして逆転させる
    vll x(N), mx(N);
    rep(i, N) {
        cin >> x[i];
        mx[N-i-1] = -x[i];
    }

    int L, Q;
    cin >> L >> Q;

    // 各iから2^j回の移動でたどり着ける点
    int logN = (int)log2(N) + 3;
    vvi dpx(N, vi(logN, -1)), dpmx(N, vi(logN, -1));
    // 初回は普通に計算
    rep(i, N) {
        {
            auto it = lower_bound(all(x), x[i] + L);
            if (*it - x[i] > L)
                --it;
            dpx[i][0] = min(N-1, (int)distance(begin(x), it));
        }
        {
            auto it = lower_bound(all(mx), mx[i] + L);
            if (*it - mx[i] > L)
                --it;
            dpmx[i][0] = min(N-1, (int)distance(begin(mx), it));
        }
    }
    // 2回目以降は、前回の移動を利用
    REP(j, 1, logN) {
        rep(i, N) {
            dpx[i][j] = dpx[dpx[i][j-1]][j-1];
            dpmx[i][j] = dpmx[dpmx[i][j-1]][j-1];
        }
    }

    while(Q--) {
        int a, b;
        cin >> a >> b;
        --a, --b;

        auto dp = begin(dpx);

        if(a > b) {
            a = N - a - 1;
            b = N - b - 1;
            dp = begin(dpmx);
        }

        int lb = 0;
        int ub = N;

        while(ub - lb > 1) {
            int med = (lb+ub) / 2;

            int pos = a;
            for(int i=31; i>=0; i--) {
                if( ((med >> i) & 1) == 1 )
                    pos = dp[pos][i];
            }

            if(pos >= b)
                ub = med;
            else
                lb = med;
        }

        cout << ub << endl;
    }

    return 0;
}

備考

 2^{j}の形で保持するのはダブリングというテクニックらしいです。
賢い。