AtCoder Beginner Contest 120

C - Unification

https://atcoder.jp/contests/abc120/tasks/abc120_c

方針

赤と青のキューブの数をそれぞれ とすると、答えは となります。

積み上げたキューブに青と赤がどちらも含まれていると、必ずどこかで青と赤が隣り合っているので、その 2 つを取り除くことが出来ます。この操作はキューブが青だけか赤だけになるまで繰り返すことが出来るので、上記の答えになります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    string S;  cin >> S;
    int n = S.length();
    // 赤と青のキューブの数をそれぞれ数える
    int r = 0, b = 0;
    for(int i=0; i<n; i++){
        if(S[i]=='0') r++;
        if(S[i]=='1') b++;
    }
    cout << 2*min(r, b) << endl;
}

D - Decayed Bridges

https://atcoder.jp/contests/abc120/tasks/abc120_d

方針

問題の設定では M 本の橋が順に崩れていきますが、問題を変えて、橋が 1 つも無い状況から、橋 M, M-1, M-2, ……, 1 の順に橋を建設していくことにします。「橋 i 崩落後」と「橋 i+1 建設後」は同じ状況になります。互いに行き来できる島の組の数を「便利さ」と呼ぶことにします。

どの2つの島についても、互いに行き来できるか、出来ないかの 2 通りしかないため、
（橋 i 崩落後の不便さ）+（橋 i + 1 建設後の便利さ）
となります。よって橋の建設後の「便利さ」を全て求めることが出来れば、この問題の答えがわかります。以降はこの問題を考えます。

島 A, B を結ぶ橋を建設することを考えます。

• A と B がもともと互いに行き来できたとき、この橋の建設によって「便利さ」は向上しません。
• A と B が互いに行き来できなかった場合、（A と行き来できる島の数 ( A 自身を含む)）×（B と行き来できる島の数 (同様)）だけ「便利さ」が増えます。

橋が 1 つも無い状況での便利さは 0 であることと併せて、上記の方針で橋の建設毎に「便利さ」を求めて行けばよいです。

例えば以下の図の場合(赤線の橋を新たに建設する)、もともとの「便利さ」は 4 で、島 1 と行き来できる島は 1 と 5 で 2 個、島 2 と行き来できるのは 2, 3, 4 の3個ですから、便利さは 2 × 3 = 6 増えて 10 となります。

橋の建設や、二つの島の行き来の判定には、union-find木を使いました。union-find木の説明は AtCoder Typical Contest 001 - B が分かりやすいです。これを用いると橋の建設は unite(A, B)、互いに行き来できるか否かの判定は find(A)==find(B) で行えます。

各島と行き来できる島の数を求めるには、union-find木において、各連結成分が頂点を何個ずつ持つかが必要になります。これは、各連結成分の根に頂点数を保持させることにし、併合の際に rank の大きい方の頂点数に小さい方の頂点数を付け加えればよいです。下記のソースコードも参考にしてください。

ソースコード

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

struct union_find{
    union_find(int n){
        for(int i=0; i<=n; i++){
            par.push_back(i);
            rank.push_back(0);
            size.push_back(1);
        }
    }
    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(rank[x] < rank[y]){
            par[x] = y;
            // x を含むグループの根は y になるので、
            // size[y] に size[x] を加える。
            size[y]+= size[x];
        }else{
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
            // 上と同様
            size[x]+=size[y];
        }
    }

    int getSize(int x){
        // 頂点 x を含む連結成分が持つ頂点数を返す。
        // 連結成分の根に頂点数を持たせるので、
        // size[x] ではなく size[find(x)]
        return size[find(x)];
    }

    private:
        vector<int> par, rank, size;
};

int main(){
    ll N, M;
    cin >> N >> M;
    vector<pair<int,int>> bridge(M+1);
    for(int i=1; i<=M; i++){
        int A, B;  cin >> A >> B;
        bridge[i] = make_pair(A, B);
    }

    union_find island(N);
    vector<ll> conv(M+2,0); // 橋 i 建設後の便利さ = conv[i]
    conv[M+1] = 0; // 橋が 1 つも無いとき便利さは 0

    // 橋 M, M-1, ……, 1 の順に橋を建設する
    for(int i=M; i>=0; i--){
        int A = bridge[i].first;
        int B = bridge[i].second;
        // A と B の根を求める
        A = island.find(A);
        B = island.find(B);
        if(A==B){
            // A, B が互いに行き来できるとき、AとBを繋いでも便利さは増えない
            conv[i] = conv[i+1];
        }else{
            // A, B が互いに行き来できないとき、
            // A, B の各グループの連結成分の数の積だけ便利さが増える
            conv[i] = conv[i+1] + island.getSize(A)*island.getSize(B);
        }
        // A と B を併合
        island.unite(A,B);
    }

    // （橋 i 崩落後の不便さ）+（橋 i + 1 建設後の便利さ）= N*(N-1)/2
    for(int i=1; i<=M; i++){
        ll ans = N*(N-1)/2 - conv[i+1];
        cout << ans << endl;
    }
}