部内勉強会（４） - octoの勉強記録

競プロライブラリ集

よく使うライブラリを紹介します

今回はライブラリの使い方だけ紹介して中身の実装の話はほとんどしません（難しいので）

Union Find Tree
Combination
DAG
セグメント木
遅延セグメント木

Union Find Tree

緑になるには必須のライブラリ

持っていると簡単に解ける問題が多数

集合を管理するデータ構想

できる操作は

同じ集合に属しているか判定　O(1)
集合の併合　O(1)
集合のサイズを取得　O(1)

集合を分離することは出来ないので注意！

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

class UnionFindTree
{
    vector<int> parent;
    vector<int> depth;
    vector<int> cnt;

public:
    UnionFindTree(int n) : parent(n), depth(n), cnt(n)
    {
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
            depth[i] = 0;
            cnt[i] = 1;
        }
    }

    //木の根を求める
    int find(int x)
    {
        if (parent[x] == x)
        {
            return x;
        }
        else
        {
            return parent[x] = find(parent[x]);
        }
    }

    //xとyの属する集合を併合
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (depth[x] < depth[y])
        {
            parent[x] = y;
            cnt[y] += cnt[x];
        }
        else
        {
            parent[y] = x;
            cnt[x] += cnt[y];
            if (depth[x] == depth[y])
                depth[x]++;
        }
    }
    // 同じ集合に属しているか判定
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
    // 集合のサイズを取得
    int size(int x)
    {
        return cnt[find(x)];
    }
};

int main()
{
    int n, m;
    cin >> n >> m;
    UnionFindTree utree(n + 10);
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        utree.unite(x, y);
    }
    map<int, int> fl;
    int ans = n;
    for (int i = 1; i <= n; i++)
    {
        if (!fl[utree.find(i)])
        {
            fl[utree.find(i)] = 1;
            ans -= utree.size(i) - 1;
        }
    }
    cout << ans << endl;
}

例題

https://atcoder.jp/contests/abc126/tasks/abc126_e

解答

https://atcoder.jp/contests/abc126/submissions/8376002

例題

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

解答

https://atcoder.jp/contests/abc120/submissions/8376028

例題

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_c

解答

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8374498

Combination

同じく緑になるには必須のライブラリ

mod上でのnCr, nPr, nHrを高速に計算する

前処理O(N)

計算O(1)

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

class Combination
{
    vector<long long> fact;
    vector<long long> factinv;
    long long MOD = 1e9 + 7;
    long long modpow(long long a, long long n)
    {
        if (n == 0)
            return 1;
        if (n % 2 == 0)
        {
            long long t = modpow(a, n / 2);
            return t * t % MOD;
        }
        return a * modpow(a, n - 1) % MOD;
    }

    long long modinv(long long a)
    {
        // mod is prime
        return modpow(a, MOD - 2);
    }

public:
    Combination(int n) : fact(n), factinv(n)
    {
        fact[0] = 1;
        for (int i = 1; i < n; i++)
        {
            fact[i] = fact[i - 1] * i % MOD;
        }
        factinv[n - 1] = modinv(fact[n - 1]);
        for (int i = n - 2; i >= 0; i--)
        {
            factinv[i] = factinv[i + 1] * (i + 1) % MOD;
        }
    }

    long long ncr(long long n, long long r)
    {
        if (r < 0 || r > n)
            return 0;
        return fact[n] * factinv[r] % MOD * factinv[n - r] % MOD;
    }

    long long npr(long long n, long long r)
    {
        if (r < 0 || r > n)
            return 0;
        return fact[n] * factinv[n - r] % MOD;
    }

    long long nhr(long long n, long long r)
    {
        if (n == 0 && r == 0)
            return 1;
        return ncr(n + r - 1, r);
    }
};

例題

https://atcoder.jp/contests/abc132/tasks/abc132_d

解答

https://atcoder.jp/contests/abc132/submissions/8375997

例題

https://atcoder.jp/contests/abc066/tasks/arc077_b

解答

https://atcoder.jp/contests/abc066/submissions/7944298

DAG

水色になるにはほしいライブラリ

有効グラフを扱うライブラリ

有向グラフ考えるときはとりあえずトポロジカルソートしたくなる

トポロジカルソート　O(N)
ループ判定　O(N)
最長経路　O(N)

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

class DAG
{
    int n;
    vector<vector<int>> adj;
    vector<int> visited;
    vector<int> dp;
    void dfs(int v)
    {
        if (visited[v] == 2)
        {
            is_acyclic = false;
            return;
        }
        else if (!visited[v])
        {
            visited[v] = 2;
            for (int s : adj[v])
            {
                dfs(s);
            }
            visited[v] = 1;
            sorted.push_back(v);
        }
    }

public:
    vector<int> sorted;
    DAG(int n) : n(n), adj(n), visited(n), dp(n, 0) {}
    bool is_acyclic = true;
    int longest_path = 0;

    //add directed link node a to node b
    void add_arc(int a, int b)
    {
        assert(0 <= a && a < n && 0 <= b && b < n);
        adj[a].push_back(b);
    }

    void tsort()
    {
        for (int i = 0; i < n; i++)
        {
            if (!visited[i])
                dfs(i);
        }
        reverse(sorted.begin(), sorted.end());
    }
    void build()
    {
        for (auto i : sorted)
        {
            for (auto j : adj[i])
            {
                dp[j] = max(dp[j], dp[i] + 1);
                longest_path = max(longest_path, dp[j]);
            }
        }
    }
};

例題

https://atcoder.jp/contests/dp/tasks/dp_g

解答

https://atcoder.jp/contests/dp/submissions/8198624

例題

https://atcoder.jp/contests/abc139/tasks/abc139_e

解答

https://atcoder.jp/contests/abc139/submissions/8079830

セグメント木

青になるまでにあると便利なデータ構造

僕は使わなくても青になれたけど使えたらもっと楽だったなってことが多かった

ある１点の更新　O(log N)
区間[L,R)での最小値の取得　O(log N)
前処理　O(N)

最小値だけでなく最大値や和など大抵の計算は扱える非常に汎用性の高いデータ構造

#include <bits/stdc++.h>
using namespace std;
// 引用http://tsutaj.hatenablog.com/entry/2017/03/29/204841
int N, Q;
int const INF = INT_MAX;

struct SegmentTree
{
private:
    int n;
    vector<int> node;

public:
    SegmentTree(vector<int> v)
    {
        int sz = v.size();
        n = 1;
        while (n < sz)
            n *= 2;
        node.resize(2 * n - 1, INF);
        for (int i = 0; i < sz; i++)
            node[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--)
            node[i] = min(node[2 * i + 1], node[2 * i + 2]);
    }

    void update(int x, int val)
    {
        x += (n - 1);
        node[x] = val;
        while (x > 0)
        {
            x = (x - 1) / 2;
            node[x] = min(node[2 * x + 1], node[2 * x + 2]);
        }
    }

    int getmin(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        if (r <= a || b <= l)
            return INF;
        if (a <= l && r <= b)
            return node[k];

        int vl = getmin(a, b, 2 * k + 1, l, (l + r) / 2);
        int vr = getmin(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
};

int main()
{
    cin >> N >> Q;
    SegmentTree seg(vector<int>(N, INF));
    for (int i = 0; i < Q; i++)
    {
        int c, x, y;
        cin >> c >> x >> y;
        if (c == 0)
            seg.update(x, y);
        else
            cout << seg.getmin(x, y + 1) << endl;
    }
}

例題

https://atcoder.jp/contests/dp/tasks/dp_q

解答

https://atcoder.jp/contests/dp/submissions/8211793

遅延セグメント木

黄色になるまでに使えると便利なデータ構造

セグメント木の上位互換

区間[L, R)の更新　O(log N)
区間[L, R)での最小値の取得　O(log N)
前処理　O(N)

最小値だけでなく最大値や和など大抵の計算は扱える

セグメント木より実装が大変なので脳死で遅延セグメント木を貼るのは危険

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

class LazySegTree
{
    int n;
    vector<long long int> node, lazy;

public:
    LazySegTree(vector<long long int> v)
    {
        int s = int(v.size());
        n = 1;
        while (n < s)
        {
            n <<= 1;
        }
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);

        for (int i = 0; i < s; i++)
        {
            node[i + n - 1] = v[i];
        }
        for (int i = n - 2; i >= 0; i--)
        {
            node[i] = node[i * 2 + 1] + node[i * 2 + 2];
        }
    }

    void eval(int k, int l, int r)
    {
        if (lazy[k])
        {
            node[k] += lazy[k];
            if (r - l > 1)
            {
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }

            lazy[k] = 0;
        }
    }

    void add(int a, int b, long long int x, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        eval(k, l, r);
        if (b <= l || r <= a)
        {
            return;
        }
        if (a <= l && r <= b)
        {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else
        {
            add(a, b, x, 2 * k + 1, l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }

    long long int rangeSum(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        eval(k, l, r);
        if (b <= l || r <= a)
        {
            return 0;
        }
        if (a <= l && r <= b)
        {
            return node[k];
        }
        long long int vl = rangeSum(a, b, 2 * k + 1, l, (l + r) / 2);
        long long int vr = rangeSum(a, b, 2 * k + 2, (l + r) / 2, r);
        return vl + vr;
    }

    void set(int a, long long int x)
    {
        add(a, a + 1, -get(a));
        add(a, a + 1, x);
    }

    long long int get(int a)
    {
        return rangeSum(a, a + 1);
    }
};

int main()
{
    int n;
    cin >> n;
    vector<long long int> as(n);
    LazySegTree seg(as);
    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        char c;
        cin >> c;
        if (c == 'A')
        {
            int id, x;
            cin >> id >> x;
            seg.set(id - 1, x);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            cout << seg.rangeSum(l - 1, r) << endl;
        }
    }
}

例題

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_d

解答

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8374973