<-- home

AtCoder ABC 157

March 2, 2020

ABC157に参加した。自分用メモ。

A B C D E F
o o o o x x

A~Dは特に問題なく解けた。Eも解法は思いついたが、セグメント木の実装にバグがあり、RE(Runtime Error)。

D-Friend Suggestions

各人の友達候補の数を計算する問題。無向グラフのノードが人、エッジが友達関係/ブロック関係になっている。 「ある人物Aの友達候補がBである」とは、

  • Aから友達関係をたどってBに到達できる
  • AとBがブロック関係になっていない
  • AとBが異なる人物

と定義される。したがって、

が求める答えになる。(Aが含まれる連結成分: 友達関係の辺で構成される連結成分)

連結成分の求め方

2つ方法がある。

  • DFSを使う
  • Union-Find木を使う

今回はDFSを使ったが、Union-Find木を用いるほうがシンプルそう。あとで実装する。

[追記] 03/05/20

Union-Find木を用いる実装

template<typename T>
struct UnionFind {
    vector<T> parent;
    vector<i64> rank;

    UnionFind(i64 n) {
        parent.assign(n, 0);
        REP(i, n) parent[i] = i;
        rank.assign(n, 1);
    }

    T find(T t) {
        if (parent[t] == t) return t;
        return parent[t] = find(parent[t]);
    }

    bool unite(T t1, T t2) {
        t1 = find(t1);
        t2 = find(t2);
        if (t1 == t2) return false;

        if (rank[t1] < rank[t2]) swap(t1, t2);
        parent[t2] = t1;
        rank[t1] += rank[t2];
        return true;
    }

    bool same(T t1, T t2) {
        return find(t1) == find(t2);
    }
};


#define MAX_N 100'000
i64 N, M, K;
vector<i64> B[MAX_N]; // ブロック関係
i64 deg[MAX_N];

int main() {
    cin >> N >> M >> K;
    fill(deg, deg + N, 0);

    UnionFind<i64> uf(N);

    i64 u, v;
    REP(i, M) {
        cin >> u >> v;
        u--; v--;
        uf.unite(u, v);
        deg[u]++;
        deg[v]++;
    }
    REP(i, K) {
        cin >> u >> v;
        u--; v--;
        B[u].pb(v);
        B[v].pb(u);
    }

    REP(u, N) {
        i64 cnt = uf.rank[uf.find(u)] - 1 - deg[u];
        for (auto it = B[u].begin(); it != B[u].end(); it++) {
            if (uf.same(u, *it)) {
                cnt--;
            }
        }
        cout << cnt << " ";
    }
    cout << endl;

    return 0;
}

E-Simple String Queries

ある文字列が与えられ、それに対する2種類のクエリがN個発行される。

  • クエリ1: 文字列のk番目の文字を変更する
  • クエリ2: 文字列のl番目からr番目からなる部分文字列を取得する

セグメント木で、各ノードが、それに対応する区間に含まれる文字の集合をもつようにすれば、高速にクエリを処理できる。今回の問題では、文字の集合を管理するのに、set<char>を使ってもいいが、文字列は英小文字からなるという制限があるので、26bitのビットフラグで集合を管理すると、処理が早いし、コードも簡潔になる。

// セグメント木のテンプレートは
// https://ei1333.github.io/luzhiled/snippets/structure/segment-tree.html
// を参考にした。1-indexedから0-indexedに変更している。
template<typename Monoid>
struct SegmentTree {
    using F = function<Monoid(Monoid, Monoid)>;

    i64 sz;
    vector<Monoid> seg;

    const F f;
    const Monoid M1;

    SegmentTree(i64 n, const F f, const Monoid &M1) : f(f), M1(M1) {
        sz = 1;
        while (sz < n) sz *= 2;
        seg.assign(2 * sz - 1, M1);
    }

    void set(i64 k, const Monoid &x) {
        seg[k + sz - 1] = x;
    }

    void build() {
        for (i64 k = sz - 2; k >= 0; k--) {
            seg[k] = f(seg[2 * k + 1], seg[2 * k + 2]);
        }
    }

    void update(i64 k, const Monoid &x) {
        k += sz - 1;
        seg[k] = x;
        while (k > 0) {
            k = (k - 1) / 2;
            seg[k] = f(seg[2 * k + 1], seg[2 * k + 2]);
        }
    }

    Monoid query(i64 l, i64 r) {
        Monoid vl = M1, vr = M1;
        for (l += sz - 1, r += sz - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
            if ((l & 1) == 0) vl = f(vl, seg[l++]);
            if ((r & 1) == 0) vr = f(seg[--r], vr);
        }
        return f(vl, vr);
    }

    Monoid operator[](const i64 &k) const {
        return seg[k + sz - 1];
    }
};

// 今回の問題では、英小文字を1 << (c - 'a')のようにbitflagにして、
// セグメント木を以下のように初期化する
// SegmentTree<i64> segtree(N, [](i64 x, i64 y){ return x | y; }, 0);