CODE THANKS FESTIVAL 2017 H - Union Sets （並列二分探索解法）

お題箱より。

H - Union Sets

「公式解説で省略されている並列二分探索について知りたい」というリクエストだったのですが、私も実装したことがなかったので調べて書いてみました。私にとっても勉強になりました。

参考資料

参考にしました。

解法

対象とする問題

並列二分探索は以下のような形式の問題を解くことができるテクニックです。

$M$ 個の操作からなる操作列があり、何らかの対象（数列や集合など）に対して順番に操作される。
以下のような形式の質問が個あり、これら全てに答える必要がある。
- 「対象がある条件 $q_{i}$ を初めて満たすのは、操作列の中の何番目が操作された後か？」
単調性がある。ある時点での操作の後に条件を満たすならば、それ以降はずっと条件が満たされている。

今回の問題「Union Sets」では各操作が集合の併合であり、質問の条件が「ある2要素が同じ集合に属していること」なので、単調性が満たされています。

このような問題を、各質問についての二分探索を並列に行うという方法で解いていきます。

処理の流れ

まずは図を見てください。質問数 $Q=3$ としています。

f:id:betrue12:20190814144249p:plain

ok ng の初期値の決め方や、条件判定の結果に応じた ok または ng の移動などは通常の二分探索と同じです。違いは判定1回ごとに操作列のシミュレートを頭から行って、各質問ごとの mid の位置に来たときに判定を行う、という点です。実装においては逆に mid の値ごとに質問を分類しておくと良いです。

操作列を何度もシミュレートするという点が計算量的に危険に見えますが、二分探索の1ループなので $O(\log M)$ 回しか回りません。今回の問題ではUnion-Find木を用いれば1回のシミュレーションは $O(N+M\alpha(N))$ 、それと各質問の判定が1ループ1回ずつなので全体計算量として $O(\log M(N+M\alpha(N) + Q))$ になります。 $\alpha(N)$ はアッカーマン関数の逆関数です。

実装＆ACコード

並列二分探索の実装だけ書くとこんな感じになります。

// 各質問について通常の二分探索のように初期値を設定（0-indexed）
vector<int> ok(Q, M), ng(Q, -1);

while(true){
    // midの値ごとに質問を分類。全質問ok-ng==1であれば終了
    bool finish = true;
    vector<vector<int>> mid_idx(M);
    for(int i=0; i<Q; i++) if(ok[i]-ng[i]>1){
        finish = false;
        int mid = (ok[i]+ng[i])/2;
        mid_idx[mid].push_back(i);
    }
    if(finish) break;

    // 操作列をシミュレートしながら、各midのタイミングで各質問について判定
    UnionFind uf(N);
    for(int i=0; i<M; i++){
        uf.unite(A[i], B[i]);
        for(int idx : mid_idx[i]) (uf.same(X[idx], Y[idx]) ? ok[idx] : ng[idx]) = i;
    }
}