Mister雑記

競プロやります。

Educational Codeforces Round #66 - E 「Minimal Segment Cover」 [???]

codeforces.com

問題

 N個の区間 [ l_i, r_i ]が与えられる。このとき、以下の M個のクエリに答えよ。

  • クエリは [ x_j, y_j ]で与えられる。
  •  [ x_i, y_i ]を上の区間で被覆できるか判定せよ。
  • できるなら被覆するのに必要な区間の数の最小値を出力せよ。

制約

  •  1 \leq N, M \leq 2 \cdot 10^5
  •  0 \leq l_i \lt r_i \leq 10^5
  •  0 \leq x_j \lt y_j \leq 10^5

考察

クエリ [ x, y ]を1つ固定して考える。

まず [x, y]を被覆するためには、 xを含むような区間を少なくとも1つ選ばなくてはならない。 この区間としてどれを選ぶべきかだが、これは r_iが最大のものが最善となることが区間スケジューリングと同じ要領で分かる。

そこで各 0 \leq x \leq 5 \cdot 10^5について、

 f(x) = 
\begin{cases}
    x & (\text{$x$を含む区間が存在しない場合}) \\
    \max\{ r_i \mid x \in [ l_i, r_i ] \} & 
\end{cases}

を前計算する。 このテーブルは区間 l_iについてソートしておけば線形時間で埋めることができる。

これを使えば、 x \to f(x) \to f(f(x)) \to \cdotsという遷移を y以上になるまで繰り返すことで解が求まる。 無限ループにハマったら被覆不能である。


しかしこのアルゴリズムの計算量は O(N)なので、全てのクエリを対処するには遅すぎる。 そこで x \to f(x) \to f(f(x)) \to \cdotsという遷移の形に着目すると、これはダブリングで高速化できることが分かる。

つまり g(x, k) = f^{2^k}(x)を各 0 \leq x \leq 5 \cdot 10^5, 0 \leq k \leq 20で求めておけば、 yを超えないようにステップ幅を選んでいくことで計算量を O(\log N)に抑えることができる。

実装例

codeforces.com

入出力高速化とcout << '\n'を両方しないとTLEになってしまった。どこか効率の悪い箇所があるのだろうか。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

constexpr int L = 500000, K = 20;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    /* ----- 入力 ----- */
    int N, Q;
    cin >> N >> Q;
    vector<pair<int, int>> segs(N);
    for (auto& s : segs) cin >> s.first >> s.second;

    /* ----- fを埋める ----- */
    sort(segs.begin(), segs.end());
    vector<vector<int>> to(K + 1, vector<int>(L + 1));

    int itr = 0, y = 0;  // 次に使う区間の番号、使われた区間中のrの最大値
    for (int x = 0; x <= L; ++x) {
        // 区間を追加していく
        while (itr < N && segs[itr].first <= x) {
            y = max(y, segs[itr].second);
            ++itr;
        }
        to[0][x] = max(x, y);
    }

    /* ----- gを埋める ----- */
    for (int k = 1; k <= K; ++k) {
        for (int x = 0; x <= L; ++x) {
            to[k][x] = to[k - 1][to[k - 1][x]];
        }
    }

    /* ----- クエリ ----- */
    for (int q = 0; q < Q; ++q) {
        int x, y;
        cin >> x >> y;

        int ans = 0;
        while (x < y) {
            if (to[0][x] == x) {  // xを被覆する区間が存在しない
                ans = -1;
                break;
            }

            int k;  // 遷移先がyより手前になるようにする
            for (k = K; k >= 0; --k) {
                if (to[k][x] < y) break;
            }

            if (k < 0) {  // 1つだけ進める(実質終了)
                ans += 1;
                x = to[0][x];
            } else {
                ans += (1 << k);  // 2^kだけ進む
                x = to[k][x];
            }
        }

        cout << ans << "\n";
    }
    return 0;
}

反省

  • ダブリングのよい練習問題という感じがする。教育的。
  • 考察も実装も十分早くて良かった。