問題概要

$ n (\leq 5000) $ 頂点 $ m (\leq 5000) $ 辺の有向グラフがある．このグラフの辺を，「含まれる辺が全て同じ色で塗られた閉路」がないように彩色したい．色の数を最小化した上で条件を満たす彩色を1つ答えよ．

解法概要

グラフが閉路を含まない場合，自明に1彩色可能．グラフが閉路を含むかどうかの判定方法はいろいろあるが，私の解法ではトポロジカルソートで全頂点を並べることができれば閉路なし，できなければ閉路ありとしている．

グラフが閉路を含む場合，1彩色は不可能である．ここで，頂点番号に着目してみる．頂点番号 $ u $ から頂点番号 $ v $ への辺があるとすると， 1つの閉路には $ u \gt v $ となるような辺と $ u \lt v $ となるような辺が必ず両方含まれる．これは例えば，$ u_1 \rightarrow u_2 \rightarrow \cdots \rightarrow u_l \rightarrow u_1 $ というような1つの閉路があるとき，以下の3つの場合に場合分けするとわかりやすい．

$ u_1 \rightarrow u_2 \rightarrow \cdots \rightarrow u_l $ の中に $ u_i \gt u_{i+1} $ となるような辺と $ u_i \lt u_{i+1} $ となるような辺が両方含まれていれば，閉路の中にも両方自明に含まれる．
$ u_1 \rightarrow u_2 \rightarrow \cdots \rightarrow u_l $ の中に $ u_i \gt u_{i+1} $ となるような辺のみなら，$ u_l \lt u_1 $ なので，閉路の中には両方含まれる．
$ u_1 \rightarrow u_2 \rightarrow \cdots \rightarrow u_l $ の中に $ u_i \lt u_{i+1} $ となるような辺のみなら，$ u_l \gt u_1 $ なので，閉路の中には両方含まれる．

したがって，$ u \gt v $ となるような辺を色1， $ u \lt v $ となるような辺を色2で彩色すれば問題の条件を満たす2彩色が可能である．また，色を3色以上使う必要はない．

ソースコード

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

using namespace std;

constexpr int MAX_N = 5000;

struct Edge {
    int u, v, color;
    Edge(int u, int v, int color): u(u), v(v), color(color) {}
};

int n, m, k = 1;
vector<int> G[MAX_N];
vector<Edge> edges;

vector<int> topological_sort(){
    int indeg[n];
    set<int> st; // 入次数が0の頂点の番号
    fill(indeg, indeg+n, 0);
    for(int i=0;i<n;++i) for(int to: G[i]) indeg[to]++;
    for(int i=0;i<n;++i) if(indeg[i] == 0) st.insert(i);

    vector<int> ret;
    int used[n];
    fill(used, used+n, 0);
    while(!st.empty()){
        int node = *st.begin();
        st.erase(node);
        ret.push_back(node);
        used[node] = 1;
        for(int next: G[node]){
            --indeg[next];
            if(!used[next] && indeg[next] == 0) st.insert(next);
        }
    }
    return ret;
}

int main() {
    cin >> n >> m;
    int u, v;
    for(int i=0;i<m;++i) {
        cin >> u >> v;
        --u; --v;
        edges.push_back(Edge(u, v, 1));
        G[u].push_back(v);
    }

    vector<int> ordered_nodes = topological_sort();
    vector<int> c(m, 1);
    if(ordered_nodes.size() == n) {
        k = 1;
    } else {
        k = 2;
        for(int i=0;i<m;++i) {
            if(edges[i].u > edges[i].v) c[i] = 2;
        }
    }

    cout << k << endl;
    for(int i=0;i<m-1;++i) cout << c[i] << " ";
    cout << c[m-1] << endl;
}

所感

ブログを更新しない間に AtCoder のレートが破滅していました．心当たりはいろいろありますが，そのうち1つが「解説ブログの更新をサボっていた」なので今週からまた1週間1記事以上を目標に頑張ります．

2019-07-08

AtCoder Beginner Contest 133 F - Colorful Tree

競技プログラミング (問題解説)

問題文: F - Colorful Tree

Writer 解説: https://img.atcoder.jp/abc133/editorial.pdf

問題概要

辺にコストと色がついた $ N (\leq 10^5) $ 頂点の木について，以下のクエリに答えよ．クエリの回数は最大 $ 10^5 $ である．

色 $ x $ の辺のコストを全て $ y $ にしたときの頂点 $ u,v $ 間のコストを答えよ．

解法概要

LCA (Lowest Common Ancestor) を求めるパート
長さの変更を反映するパート

に分けて考える．

LCA はダブリングを使った方法などで求めると時間計算量 $ O(N \log N)$ で求められるので，$ u_i$と$ v_i$ のLCAが$ l_i$とわかっているものとして 2. について考える．

根から頂点$ i$までの経路について，その長さを$ d_i$，色$ x$ の辺の長さの和を$ d_{i,x}$，色$ x$の辺の本数を$ n_{i, x}$とすると，各クエリの答えは

$ (d_u+d_v-d_l) -(d_{u,x}+d_{v,x}-d_{l,x}) + y_i (n_{u_i,x_i}+n_{v_i,x_i}-2n_{l_i,x_i})$

$ d_{i,x}$ と$ n_{i,x}$ を全て求めようとすると時間計算量・空間計算量ともに$ O(N^2)$ となってしまい，間に合わない．これはクエリを先読みして必要な部分だけを map などに保管するようにすれば，時間計算量は$ O(N\log Q)$，空間計算量は$ O(Q)$に抑えることができる． (計算量の見積もりは怪しい．特に$ N$と$ Q$ を混同している可能性がある)

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

using ll =  long long;

constexpr ll V_MAX = 100010;

vector<tuple<int, int, ll>> graph[V_MAX];
vector<ll> dists(V_MAX);
map<ll, int> colormp;
map<ll, ll> distmp;
set<int> required_colors[V_MAX];

class LowestCommonAncestor {
    public:
    int root, n, LOG_V_MAX = 20;
    vector<int> depth;
    vector<vector<int>> parent;

    LowestCommonAncestor(int root=0, int n=V_MAX): root(root), n(n) {
        depth.assign(n, -1);
        parent.assign(n, vector<int>(LOG_V_MAX, -1));
        dfs(root, -1, 0);
        for(int j=1;j<LOG_V_MAX;++j) {
            for(int i=0;i<n;++i) {
                if(parent[i][j-1] == -1) continue;
                parent[i][j] = parent[parent[i][j-1]][j-1];
            }
        }
    }

    void dfs(int node, int par, int d) {
        depth[node] = d;
        parent[node][0] = par;
        for(auto child: graph[node]) {
            int c = get<0>(child);
            if(c == par) continue;
            dfs(c, node, d+1);
        }
    }

    int get_lca(int u, int v) {
        if(depth[u] > depth[v]) swap(u, v);
        int depth_diff = depth[v] - depth[u];
        for(int j=0;j<LOG_V_MAX;++j) {
            if(depth_diff & (1 << j)) {
                v = parent[v][j];
            }
        }
        if(u == v) return u;
        for(int j=LOG_V_MAX-1;j>=0;--j) {
            if(parent[u][j] != parent[v][j]) {
                u = parent[u][j];
                v = parent[v][j];
            }
        }
        return parent[u][0];
    }
};

void dfs(int node, int par, ll dist, map<ll, int> &cmp, map<ll, ll> &dmp) {
    dists[node] = dist;
    for(int color: required_colors[node]) {
        colormp[V_MAX*node+color] = cmp[color];
        distmp[V_MAX*node+color] = dmp[color];
    }
    int chi, color; ll di;
    for(auto child: graph[node]) {
        tie(chi, color, di) = child;
        if(chi == par) continue;
        dist += di;
        ++cmp[color];
        dmp[color] += di;
        dfs(chi, node, dist, cmp, dmp);
        dist -= di;
        --cmp[color];
        dmp[color] -= di;
    }
}

int main() {
    int n,q;
    cin >> n >> q;
    int a,b,c; ll d;
    for(int i=0;i<n-1;++i){
        cin >> a >> b >> c >> d;
        --a; --b; --c;
        graph[a].push_back(make_tuple(b, c, d));
        graph[b].push_back(make_tuple(a, c, d));
    }

    LowestCommonAncestor lca = LowestCommonAncestor(0, n);

    vector<tuple<int,ll,int,int,int>> query(q);
    int u,v,l,x; ll y;
    for(int i=0;i<q;++i) {
        cin >> x >> y >> u >> v;
        --x; --u; --v;
        l = lca.get_lca(u, v);
        query[i] = make_tuple(x, y, u, v, l);
        required_colors[u].insert(x);
        required_colors[v].insert(x);
        required_colors[l].insert(x);
    }

    {
        map<ll, int> mp1;
        map<ll, ll> mp2;
        dfs(0, -1, 0, mp1, mp2);
    }

    for(int i=0;i<q;++i) {
        tie(x, y, u, v, l) = query[i];
        ll ans = (dists[u]+dists[v]-2*dists[l]) - (distmp[V_MAX*u+x]+distmp[V_MAX*v+x]-2*distmp[V_MAX*l+x]) + y*(colormp[V_MAX*u+x]+colormp[V_MAX*v+x]-2*colormp[V_MAX*l+x]);
        cout << ans << endl;
    }
}

所感

†プログラミングコンテスト† って感じで好き．

仮にまたKatsuT0shi でチーム戦に参加するとしてこういう問題が出たら私の担当だよな〜．ICPCは引退済みだけど重実装担当を自負する者としてこういう問題には強くありたい．

2019-06-18

AtCoder Regular Contest 096 E - Everything on It

競技プログラミング (問題解説)

問題文: E - Everything on It

Writer 解説: https://img.atcoder.jp/arc096/editorial.pdf

問題概要

ラーメンに $ N (\leq 3000)$ 種類のトッピングを乗せて注文する．乗せるトッピングの数に制限はなく，全部乗せることも全部乗せないこともできるので，トッピングの乗せ方は $ 2^N $ 通りある．

以下 2 つの条件を満たすラーメンの注文の仕方が何通りあるかを，$ \mathit{M}$ で割った余りをとって答えよ．

トッピングの組み合わせがまったく同じラーメンを複数杯注文しない．
$ N $ 種類のトッピングそれぞれが，注文したラーメンのうち 2 杯以上に乗っている．

解法概要

「すべてのトッピングが2回以上使われる」よりも「1回以下しか使われないトッピングがある」を数えた方が，トッピングの使われる回数について0回 / 1回だけ考えれば済んで良さそう．なので，数え上げる条件を「1回以下しか使われないトッピングがある」と考え，包除原理を用いる．つまり，

(1回以下しか使われないトッピングが0個以上ある) - (1回以下しか使われないトッピングが1個以上ある) + (1回以下しか使われないトッピングが2個以上ある) - ...

のような計算をすれば良い．

ここで，1回以下しか使われないトッピングが $ i$ 個以上ある場合に対応する項について考える．

この1回以下しか使われない$ i $種類のトッピングのいずれか1種類以上を含むようなラーメンが$ j$杯あったとしたときの$ i$種類のトッピングの分け方を$ f(i, j)$ とすると，$ f(i, j) = f(i-1, j) + f(i-1, j-1) + jf(i-1, j) = f(i-1, j-1) + (j+1)f(i-1, j)$のような Stirling 数のような漸化式が立てられる．$ f(i-1, j) $ は i 番目のトッピングを使わない場合，$ f(i-1, j-1) $ は i-1 番目までのトッピングを乗せていないラーメンに i 番目のトッピングを乗せる場合，$ jf(i-1, j) $ 他の "1回以下しか使われないことが確定しているトッピング" が乗っているラーメンに i 番目のトッピングも乗せる場合に対応する．

これを用いると，$ i $種類のトッピングのいずれか1種類以上を含むようなラーメンが$ j$杯あったとしたときのラーメンの注文方法の通り数は$ f(i, j) \times 2^{(N-i)j} \times 2^{2^{N-i}}$．$ 2^{(N-i)j} $ は $ i $種類のトッピングのいずれか1種類以上を含むような$ j$杯のラーメンにに対する，$ i $種類のトッピング以外のトッピングの乗せ方のパターン数である．また，$ 2^{2^{N-i}} $ は，$ j$杯のラーメン以外に注文するラーメンの注文方法に対応している．$ N-i$種類のトッピングの組み合わせ方は$ 2^{N-i} $ 通りで，そのそれぞれについて，注文する / しないが選べるためである．

また，$ N $種類のトッピングから $ i $種類選ぶ選び方は$ {}_N C_{i} $ 通りなので，$ i$ 種類以上のトッピングが1回以下しか使われないような注文の仕方の通り数は $ 2^{2^{N-i}} {}_N C_{i} \sum_{j=1}^{i} 2^{(N-i)j} f(i, j) $ となる．あとはこれを最初に包除原理を使って変形した式にぶちこむ．

2の累乗や2の2乗の累乗を事前に計算しておけば間に合う．

ソースコード

#include <iostream>

using namespace std;

using ll =  long long;

constexpr int N_MAX = 3001;

ll MOD;
ll s[N_MAX][N_MAX], pow2[N_MAX*N_MAX], powpow2[N_MAX];

void init_stirling(int n, int m) {
    for(int i=0;i<=n;++i) s[i][0] = 1;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            s[i][j] = (s[i-1][j-1] + (s[i-1][j]*(j+1)) % MOD) % MOD;
        }
    }
}

ll fact[N_MAX], rfact[N_MAX];

ll perm(ll n, ll r){
    return (fact[n] * rfact[r]) % MOD;
}

ll comb(ll n, ll r){
    return (perm(n, r) * rfact[n-r]) % MOD;
}

void init(ll n){
    fact[0] = fact[1] = 1;
    rfact[0] = rfact[1] = 1;
    for(int i=2;i<=n;++i) {
        fact[i] = (fact[i-1] * (ll)i) % MOD;
        rfact[i] = 1;
        ll k = MOD-2;
        ll a = fact[i];
        while(k > 0){
            if(k & 1){
                rfact[i] *= a;
                rfact[i] %= MOD;
            }
            a *= a;
            a %= MOD;
            k  >>= 1;
        }
    }
}

ll modpow(ll a, ll t) {
    ll ret = 1LL;
    while(t){
        if(t & 1LL){
            ret *= a;
            ret %= MOD;
        }
        a *= a;
        a %= MOD;
        t >>= 1;
    }
    return ret;
}

int main() {
    ll n;
    cin >> n >> MOD;
    init(n);
    init_stirling(n, n);

    pow2[0] = 1LL;
    for(int i=0;i<n*n;++i) {
        pow2[i+1] = (2LL * pow2[i]) % MOD;
    }
    powpow2[0] = 2LL;
    for(int i=0;i<n;++i) {
        powpow2[i+1] = (powpow2[i] * powpow2[i]) % MOD; // 2^(2^n) = 2^(2^(n-1)) * 2^(2^(n-1))
    }

    ll ans = powpow2[n];
    for(ll i=1;i<=n;++i) {
        ll tmp = 0LL;
        for(ll j=0;j<=i;++j) {
            if(pow2[(n-i)*j] == 0) {
                pow2[(n-i)*j] = modpow(2LL, (n-i)*j);
            }
            tmp += pow2[(n-i)*j] * s[i][j];
            tmp %= MOD;
        }
        tmp *= comb(n, i);
        tmp %= MOD;
        tmp *= powpow2[n-i];
        tmp %= MOD;
        if(i % 2) {
            ans += MOD - tmp;
        } else {
            ans += tmp;
        }
        ans %= MOD;
    }

    cout << ans << endl;

}

所感

第二種スターリング数を学んだ問題その2．

$ 2^{2^{N+1}} = 2^{2^N} \times 2^{2^N} $ の変形ができなくて自分の算数力の無さにびっくりしちゃった．

NoiminのNoise

Educational Codeforces Round 72 D. Coloring Edges

問題概要

解法概要

ソースコード

所感

AtCoder Beginner Contest 133 F - Colorful Tree

問題概要

解法概要

ソースコード

所感

AtCoder Regular Contest 096 E - Everything on It

問題概要

解法概要

ソースコード

所感