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

なんだかんだ 3 完できてうれぴー。

問題

arc060.contest.atcoder.jp

解法

クエリでは a < b として良いです。

戦略としては, 「その日にたどり着けるところまでなるべく遠くへ行く」というのが明らかに最適です。ということで, nxt[0][i] = (頂点 i からなるべく遠くへ行こうとしたときたどり着く頂点) というのをあらかじめメモしておきます。これは二分探索を使えば各 i について O(log N) でできます。

で, nxt[j+1][i] = nxt[j][nxt[j][i]] というのを繰り返すことにより, i から 2^j 日貪欲に移動した際にたどり着ける最も遠い頂点を得ます。これがあれば各クエリに対して二分探索をして O(log N) で答えを求められます。

クエリでの二分探索の書き方は蟻本の LCA と同じです。b の直前になるところまで行って, 後 +1 みたいな感じ。

const int MAXN = 100100;
int N, L, Q;
int X[MAXN];

int nxt[20][MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N; 
    for (int i = 0; i < N; i++)
        cin >> X[i];
    cin >> L;
    memset(nxt, -1, sizeof(nxt));
    for (int i = 0; i < N; i++) {
        if (i == N-1) {
            nxt[0][i] = N-1;
            continue;
        }
        int low = i+1, high = N;
        while (high-low > 1) {
            int med = (high+low)/2;
            if (X[med] - X[i] <= L) low = med;
            else high = med;
        }
        nxt[0][i] = low;
    }
    for (int i = 0; i < 20-1; i++) {
        for (int j = 0; j < N; j++) {
            if (nxt[i][j] == -1) nxt[i+1][j] = -1;
            else nxt[i+1][j] = nxt[i][nxt[i][j]];
            assert(nxt[i][j] != -1);
        }
    }
    cin >> Q;
    for (int t = 0; t < Q; t++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (a > b) swap(a, b);
        if (a < b) {
            int ans = 0;
            for (int i = 20-1; i >= 0; i--) {
                if (nxt[i][a] < b) {
                    a = nxt[i][a];
                    ans |= 1<<i;
                }
            }
            cout << ans+1 << endl;
        }
    }
    return 0;
}