平成最後の日も蟻本の勉強をしてみた. 二分木, 二分探索木, Union-Find木を使った問題を3問解いた.

priority_queueを用いる問題

1 expedition

ガソリンを補給する回数を最小限に抑える問題. 探索としては, 今あるガソリンで次のガソリンスタンドに辿り着けなかったら, 過去に通過した供給量が一番大きいガソリンスタンドで補給したことにする. ここで, ガソリンスタンドをpriority_queueに入れて, 供給量が大きいもの順に並べていた.


#include 
#include 
using namespace std;
const int MAX_N = 10000;
int N, L, P;
int A[MAX_N + 1], B[MAX_N + 1];
void read() {
    cin >> N >> L >> P;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }
}
void solve() {
    A[N] = L;
    B[N] = 0;
    priority_queue que;
    int ans = 0, pos = 0, tank = P;
    for (int i = 0; i <= N; i++) {
        int d = A[i] - pos;
        // ガソリンを補給
        while (tank - d < 0) {
            if (que.empty()) {
                puts("-1");
                return;
            }
            tank += que.top();
            que.pop();
            ans++;
        }
        tank -= d;
        pos = A[i];
        que.push(B[i]);
    }
    printf("%d\n", ans);
}
int main(int argc, char const *argv[]) {
    read();
    solve();
    return 0;
}

2 fence repair

なるべく長い板を切らせないように目的の板の集合を手に入れる問題. ナイーブに実装するとO(N^2)時間になってしまうが, priority_queueを用いればO(NlogN)時間になる.


const int MAX_N = 10000;
int n, l[MAX_N];
void solve() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> l[i];
    }
    LL ans = 0;
    priority_queue, greater > que;
    for (int i = 0; i < n; i++) {
        que.push(l[i]);
    }
    while (que.size() > 1) {
        int l1, l2;
        l1 = que.top();
        que.pop();
        l2 = que.top();
        que.pop();
        ans += l1 + l2;
        que.push(l1 + l2);
    }
    printf("%lld\n", ans);
}
int main() {
    solve();
    return 0;
}

priority_queueの小さい順

priority_queue<int, vector<int>, greater<int> > que;

このように宣言する.

3 食物連鎖

複数の情報から矛盾している情報の数を求める. 食物連鎖の関係に矛盾がないことを調べるのにUnion-Find木を用いる. 情報を見ると, 同じ種類に属するか捕食被食の関係にあるという情報だけで種類を特定できない. そこで, 3通りのUnion-Find木を作って1つの木が同時に実現するということにする.

以下がUnion-Find木の実装である.

// union find
// --------------------------------------------
int par[MAX_N];
int depth[MAX_N];
// 初期化
void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        depth[i] = 0;
    }
}
// 木の根を返す
int find(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}
// 木を併合する
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (depth[x] < depth[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (depth[x] == depth[y]) depth[x]++;
    }
}
bool same(int x, int y) { return find(x) == find(y); }
int N, K;
int T[MAX_K], X[MAX_K], Y[MAX_K];
void solve() {
    cin >> N >> K;
    for (int i = 0; i < K; i++) {
        cin >> T[i] >> X[i] >> Y[i];
    }
    init(N * 3);
    int ans = 0;
    for (int i = 0; i < K; i++) {
        int t = T[i];
        int x = X[i] - 1, y = Y[i] - 1;  // 0...N-1
        // 正しくない番号
        if (x < 0 || x >= N || y < 0 || y >= N) {
            ans++;
            continue;
        }
        if (t == 1) {
            // xとyは同じ種類という情報
            if (same(x, y + N) || same(x, y + N * 2)) {
                ans++;
            } else {
                unite(x, y);
                unite(x + N, y + N);
                unite(x + N * 2, y + N * 2);
            }
        } else {
            if (same(x, y) || same(x, y + N * 2)) {
                ans++;
            } else {
                unite(x, y + N);
                unite(x + N, y + N * 2);
                unite(x + N * 2, y);
            }
        }
    }
    printf("number of wrong info is %d\n", ans);
}
int main() {
    solve();
    return 0;
}

感想

Union-Find木を知らなかったので, 食物連鎖の実装が綺麗でわかりやすかった. これも標準のライブラリがあればいいのに…