pekempelog

ペケンペイのブログ

Connecting Cities

https://atcoder.jp/contests/keyence2019/tasks/keyence2019_e

ブルーフカで やった。こういう もっとも おもいエッジだけなら わかる みたいなのは ブルーフカが うまくいきやすいかも。


ブルーフカについて かくまえに MST でよくつかうセイシツに ふれよう。つぎのふたつが よくつかわれる。

cut property: あるカット (X,V-X) をみたとき X から V-X に のびているエッジのうち もっとも おもいエッジは つかってよい
cycle property: あるサイクルをみたとき そのなかで もっとも かるいエッジは つかわなくてよい

これはボクが かんがえたわけではなくて [1] や [2] で いわれているもの。プリムもクラスカルもブルーフカも cut property のアルゴリズムだけど cycle property もみおぼえがあるはず。

ブルーフカのアルゴリズム

まず あるノードから はえている もっとも おもいエッジは つかってよい (cut property)。すべてノードで このことがいえるので これらのエッジを すべて つかってしまう。ただし サイクルが できてしまうエッジは つかわなくてもいい。

つぎに あるレンケツセイブンから はえているエッジのうち もっとも おもいエッジは つかってよい (cut property)。 すべてレンケツセイブンで このことがいえるので これらのエッジを すべて つかってしまう。

これをくりかえすことで MST がつくれる。レンケツセイブンのかずが N->N/2->N/4->N/8->... となるから O(M log N) である。

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

using namespace std;

#define SEG (1 << 18)

const long long inf = 2e18;

struct segtree {
    pair<long long, int> dat[SEG * 2];

    void update(int k, long long v, int id) {
        k += SEG;
        dat[k] = {v, id};
        while (k > 1) {
            k >>= 1;
            dat[k] = min(dat[k * 2], dat[k * 2 + 1]);
        }
    }

    pair<long long, int> query(int l, int r) {
        l += SEG;
        r += SEG;
        pair<long long, int> res(inf, -1);
        while (l < r) {
            if (l & 1) res = min(res, dat[l++]);
            if (r & 1) res = min(res, dat[--r]);
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

segtree L, R;

vector<int> dat[200000];
int par[200000];

int find(int u) {
    if (par[u] == u) return u;
    return par[u] = find(par[u]);
}

void unite(int u, int v) {
    u = find(u);
    v = find(v);
    if (dat[u].size() < dat[v].size()) {
        swap(u, v);
    }
    dat[u].insert(dat[u].end(), dat[v].begin(), dat[v].end());
    par[v] = u;
}

int N;
long long D;
long long A[200000];

int main() {
    scanf("%d %lld", &N, &D);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
        par[i] = i;
        dat[i].push_back(i);
    }
    int c = N;
    long long ans = 0;
    while (c >= 2) {
        for (int i = 0; i < N; i++) {
            L.update(i, A[i] - i * D, find(i));
            R.update(i, A[i] + i * D, find(i));
        }
        vector<long long> cost;
        vector<int> from;
        vector<int> to;
        for (int i = 0; i < N; i++) {
            if (find(i) != i) continue;
            pair<long long, int> mn(inf, -1);
            for (int j : dat[i]) {
                L.update(j, inf, find(j));
                R.update(j, inf, find(j));
            }
            for (int j : dat[i]) {
                auto x = L.query(0, j);
                auto y = R.query(j, N);
                x.first += A[j] + j * D;
                y.first += A[j] - j * D;
                mn = min(mn, x);
                mn = min(mn, y);
            }
            for (int j : dat[i]) {
                L.update(j, A[j] - j * D, find(j));
                R.update(j, A[j] + j * D, find(j));
            }
            cost.push_back(mn.first);
            from.push_back(i);
            to.push_back(mn.second);
        }
        for (int i = 0; i < cost.size(); i++) {
            if (find(from[i]) == find(to[i])) continue;
            unite(from[i], to[i]);
            ans += cost[i];
            c--;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

セグツリーをつかわずに max の top2 をもてば O(N log N)

[1] D. R. Karger, P. N. Klein, R. E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, JACM, 42(2), 332–328, 1995.
[2] R. E. Tarjan, Data Structures and Network Algorithms, SIAM, 1989.