2014 ACM-ICPC World Finals K - Surveillance

問題のリンク：https://www.acmicpc.net/problem/10060

問題概要

$n$ 個の点が円環上に並んでいる。また $k$ 個の区間が与えられる。$n$ 個の点を全て覆えるような区間の最小数を出力せよ。

制約

$3 \le n \le 10 ^ {6} , 1 \le k \le 10 ^ {6} $

解法

円環を切り開く位置を全探索。ダブリングテーブル上の二分探索で $O(n\log{n})$。

実装

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

int main() {
    int n, k; cin >> n >> k;
    vector<int> mxr(n * 2 + 1);
    iota(mxr.begin(), mxr.end(), 0);
    for (int i = 0; i < k; ++i) {
        int l, r; cin >> l >> r;
        l -= 1, r -= 1;
        if (l <= r) {
            mxr[l] = max(mxr[l], r + 1);
            mxr[l + n] = max(mxr[l + n], r + n + 1);
        } else {
            mxr[l] = max(mxr[l], r + n + 1);
            mxr[l + n] = max(mxr[l + n], 2 * n);
        }
    }
    for (int i = 1; i < mxr.size(); ++i) {
        if (mxr[i - 1] > i) mxr[i] = max(mxr[i], mxr[i - 1]);
    }
    vector<vector<int>> d(21, vector<int>(2 * n + 1));
    for (int i = 0; i <= 2 * n; ++i) {
        d[0][i] = mxr[i];
    }
    for (int i = 1; i <= 20; ++i) {
        for (int j = 0; j <= 2 * n; ++j) {
            d[i][j] = d[i - 1][d[i - 1][j]];
        }
    }
    int res = 1e9;
    for (int i = 0; i < n; ++i) {
        if (d[20][i] - i < n) continue;
        int ng = 0;
        int cur = i;
        for (int j = 20; j >= 0; --j) {
            if (d[j][cur] - i < n) {
                ng += (1 << j);
                cur = d[j][cur];
            }
        }
        res = min(res, ng + 1);
    }
    if (res == 1e9) cout << "impossible" << endl;
    else cout << res << endl;
}

コメント

簡単枠なんだけど、こういう既出探すの苦労しそうなのでブログにした。

あと、ltst の実装覗いたら $O(n+k)$ で解けると書いてあった。深追いしてないです。