Expected diameter of a tree | Codeforces #411

コメントつきコード

// 頂点の数、辺の数、連結成分のID、最も遠い点までの距離、連結成分の直径
int N, M, Q, cmp[100001], far[100001], nc, dia[100001];
// グラフ、連結成分ごとに最も遠い点までの距離をすべてもってソートしたもの
vi G[100001], F[100001];
// その部分和
vll S[100001];
// メモ
map<pii, ll> DS;

int bfs(int root, int c) {
    queue<tuple<int,int,int> > q;
    q.push({ root,-1, 0});
    int ma = -1, fa = 0;
    while (sz(q)) {
        int u, p, d;
        tie(u, p, d) = q.top();
        q.pop();
        cmp[u] = c;
        if (d > ma) {
            fa = u;
            ma = d;
        }
        /*
        頂点uから最も遠い点までの距離を求める。
        */
        smax(far[u], d);
        each(v, G[u])if (v != p) {
            q.push({ v,u,d + 1 });
        }
    }
    return fa;
}

ll solve(int U, int V) {
    if (DS.count({ U,V }))return DS[{U, V}];
    int madi = max(dia[U], dia[V]);
    ll &res = DS[{U, V}];
    /*
    ここの最悪ケースを考えてみよう。
    すべての連結成分の大きさが√nのとき
    √n個のUについてxは√N個あり、相手のVがc√N個
    中で二部探索しているので
    O(n^(3/2)log(n))
    **/
    each(x, F[U]) {
        /*
        madi > x + y
        連結しても直径はmadiのまま
        madi <= x + yのとき
        連結すると直径は
        x + y + 1
        y ∈ F[V]
        最小のyを求める
        madi - x <= y
        */
        int k = (int)distance(F[V].begin(), lower_bound(all(F[V]), madi - x));
        res += (ll)k*madi;
        // madi<=x+y
        // x+y+1のx+1の部分を足す
        res += (ll)(x + 1)*(sz(F[V]) - k);
        // x+y+1のyを足す
        res += S[V].back() - S[V][k];
    }
    return res;
}

int main(){
    cin >> N >> M >> Q;
    rep(i, M) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u; --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    MEM(cmp, -1);

    /*
    各木について直径を求める。
    また、頂点vから最も遠い点までの距離をすべて求める。
    */
    rep(i, N) if (cmp[i] == -1) {
        // iから最も遠い頂点はx
        int x = bfs(i, nc);
        // xから最も遠い頂点はy
        int y = bfs(x, nc);
        // (x, y)の距離が直径
        dia[nc] = far[y];
        // 任意の頂点についてxまたはyが最も遠い頂点の1つである。
        bfs(y, nc);
        nc++;
    }
    
    /*
    最も遠い点までの距離たちを連結成分ごとにまとめてからソートする
    */
    rep(i, N)F[cmp[i]].push_back(far[i]);
    rep(i, nc) {
        sort(all(F[i]));
        S[i].resize(sz(F[i]) + 1);
        rep(j, sz(F[i])) {
            S[i][j + 1] = F[i][j] + S[i][j];
        }
    }

    while (Q--) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u;
        --v;
        int U = cmp[u], V = cmp[v];
        if (U == V) {
            printf("%d\n", -1);
            continue;
        }
        if (sz(F[U]) > sz(F[V]))swap(U, V);
        ll x = solve(U, V);
        double ans = (double)x / sz(F[U]) / sz(F[V]);
        printf("%0.10f\n", ans);
    }
}
広告を非表示にする

Find Amir | Codeforces #411

2番目の入力例n=10を考えてみよう。

とりあえず、(i+j) mod (n+1) = 0

となるような辺(i, j)はコスト0なので全部張ろう。

1-10

2-9

3-8

4-7

5-6

あとはコスト1以上の辺を貼るしかない。

実はすべてコスト1の辺で繋げられる。

10+2≡1

9+3≡1

8+4≡1

7+5≡1

よってコストは4。

奇数の場合も同様に考えることができる。したがって解は

floor((n-1)/2)

 

クラスカル法っぽくやる

広告を非表示にする

Minimum number of steps | Codeforces #411 (Div. 1)

abのような形が残らないので、操作していくと最終的に

bbb....baa...a

のような形になる。

とりあえず実験してみる。

ab

→bba

bはaを飛び越えるときに1個から2個になった。

abに対する操作は1回。

aab

→a<ab>

abba

→<ab>ba

→bbaba

→bb<ab>a

→bbbbaa

aを2個飛び越えることでbは4個になった。

abに対する操作は1+2回。

...

k>=1のとき

(aがk個)b→(bが2^k個)(aがk個)

abに対する操作は1+2+...+2^(k-1) 回

 

あとは、すべてのbについて、そのbより左にあるaを数えて、この操作回数の和を求めればいい。

広告を非表示にする

Ice cream coloring | Codeforces #411 (Div. 1)

コメント付きコード

// 頂点の数、色の数、頂点vに含まれるアイスの数
int N, M, S[300001];
// グラフ, 頂点vに含まれるアイス
vi G[300001], C[300001];
// 解, 色iを使ったかどうか
int X[300001], use[300001];

int main(){
    scanf("%d%d", &N, &M);
    rep(i, N) {
        scanf("%d", &S[i]);
        C[i].resize(S[i]);
        rep(j, S[i])scanf("%d", &C[i][j]), --C[i][j];
    }
    rep(i, N - 1) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u; --v;
        /*
        S[u] > 0 かつ S[v] > 0の場合だけ辺を張る。
        こうすると元の木Tの部分木の集合(Tの分割)が得られる。
        アイスは連結した部分グラフになっているので、どのアイスもたかだか1個の部分木にしか現れない。
        */
        if (S[u] && S[v]) {
            G[u].push_back(v);
            G[v].push_back(u);
        }
    }

    int ans = 1;
    queue<pii> q;
    rep(i, N) {
        /*
        頂点iの含む部分木に含まれるアイスの色をすべて決める。
        */
        if (S[i] && !X[C[i][0]]) {
            /*
            部分木を頂点ごとに探索していく。スタックオーバーフローを避けるためにDFSはしない。
            */
            q.push(mp(i, -1));
            while (sz(q)) {
                int u, pre;
                tie(u, pre) = q.front();
                q.pop();
                /*
                すでに色が確定しているアイスをチェック
                */
                rep(j, S[u]) {
                    int ice = C[u][j];
                    if (X[ice]) {
                        use[X[ice]] = 1;
                    }
                }
                /*
                1から順に、まだ使われていない色を探していく。
                */
                int cur = 1;
                rep(j, S[u]) {
                    int ice = C[u][j];
                    if (!X[ice]) {
                        // 色curは他のアイスに使われている。
                        while (use[cur])cur++;
                        X[ice] = cur;
                        use[cur] = 1;
                    }
                }
                /*
                curが最大値を取るとき、
                色1, 2, 3, 4, 5, ... , cur
                はすべて使われている。
                逆にこの時、curを一色でも減らすと、必ずどこかで同色が隣接してしまう。
                */
                smax(ans, cur);
                rep(j, S[u])use[X[C[u][j]]] = 0;
                each(v, G[u]) if (v != pre) {
                    q.push(mp(v, u));
                }
            }
        }
    }

    /*
    問題文には
    "empty set of vertices form a connected subgraph in this problem"
    とあるので、アイスが空の部分木になっている場合がある。
    このアイスの色は任意なので1をふっておく。
    人々が落ちてるのはここ?
    */
    rep(i, M)if (!X[i])X[i] = 1;

    printf("%d\n", ans);
    rep(i, M) {
        printf("%d%c", X[i], i != M - 1 ? ' ' : '\n');
    }
}
広告を非表示にする

Subsequence Queries | CS Academy #24

コメントつきコード

/*
解法
漸化式で解を表して行列を作ってみる。
行列は添字ごとに異なるので累乗では解けない。
[l, r)の積
A[r-1]A[r-2]...A[l]
の求め方

(1) セグメント木を使って求める
http://yukicoder.me/problems/no/510
の解法
今回の問題ではTLEを食らった
(2)
逆行列を使う
A[r-1]A[r-2]...A[l]
= A[r-1]A[r-2]...A[l]...A[0]inv(A[0])inv(A[1])...inv(A[l-1])
ただし、inv(A[i])は行列A[i]の逆行列とする。
*/

/*
行列Bの左から行列Aを掛けた積を返す
*/
const int MOD = (int)1e9 + 7;
vector<vector<int> > mulMatMod(const vector<vector<int> > &A, const vector<vector<int> > &B) {
    auto n = A.size(), m = A[0].size(), p = B[0].size();
    vector<vector<int> > res(n, vector<int>(p));
    for (int i = 0; i < n; ++i)for (int j = 0; j < p; ++j) for (int k = 0; k < m; ++k)
        res[i][j] = (int)((res[i][j] + (long long)A[i][k] * B[k][j]) % MOD);
    return res;
}

typedef vector<vector<int> > mat;
string S;
int Q;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> S >> Q;
    int N = sz(S);
    mat E(10, vi(10));
    rep(i, 10)E[i][i] = 1;
    vector<mat> AA(N+1, E), BB(N+1, E);
    rep(i, N) {
        int a = S[i] - 'a';
        mat A = E;
        // B=inv(A)
        mat B = E;
        rep(j, 10)A[a][j] = 1;
        // 掛ける順番に注意
        // A[j]A[j-1]...A[0]
        AA[i + 1] = mulMatMod(A, AA[i]);
        /*
        1 0 0 0 0
        1 1 1 1 1
        0 0 1 0 0
        0 0 0 1 0
        0 0 0 0 1
        のように漸化式から作った行列が特殊な形をしているので
        逆行列を簡単に求めることができる。
        */
        rep(r, 10)if (r != a) {
            B[a][r] = (B[a][r] + MOD - 1) % MOD;
        }
        // B[0]B[1]...B[j]
        BB[i + 1] = mulMatMod(BB[i], B);
    }

    mat u(10, vi(1));
    u[9][0] = 1;
    while (Q--) {
        int l, r;
        cin >> l >> r;
        --l;
        // A[l, r) = A[r-1]...A[0]inv(A[0])inv(A[1])...inv(A[l-1])
        mat Alr = mulMatMod(AA[r], BB[l]);
        ll ans = 0;
        rep(i, 9)ans += Alr[i][9];
        cout << ans%MOD << endl;
    }
}
広告を非表示にする

Counting Perfect Subsequences | HourRank 20

sに含まれる文字xの数をn(x)とする。
c, dが無いものと見做してsがa, bだけから成り立つと考えてみよう。
f[i]を文字a, bをちょうどi個ずつ含む部分列の数とする。
i>min(n(a), n(b))のとき
aまたはbの数が足りないから
f[i] = 0
i<=min(n(a), n(b))のとき
n(a)個のaのうちi個の選び方はC(n(a), i)
n(b)個のbのうちi個の選び方はC(n(b), i)
よって
f[i] = C(n(a), i)*C(n(b), i)

同様にc, dだけを考えてg[j]をc, dをちょうどi個含む部分列の数とすれば
g[j] = C(n(c), j)*C(n(d), j)

あとは、空の部分列になる(0, 0)以外のすべての(i, j)の組について考えれば良いので
ans
= Σ(f[i]g[j])-1
= Σ(f[i]) * Σ(g[i]) - 1
で求まった。

この数式変形はよくある。例えば、
1*4+1*5+1*6 + 2*4+2*5+2*6 + 3*4+3*5+3*6
= (1+2+3)*(4+5+6)

広告を非表示にする

Birjik and Nicole's Tree Game | HourRank 20

復習用コメント付きコード

/*
思いつき方
頂点を黒く塗る
その黒い頂点を含む部分木は?
根まで行く距離が長過ぎる
HL分解する
*/

/*
HL分解
Heavy-Light Decomposition
木の構築 O(|V|+|E|)
あらかじめ与えられた木について、頂点u,v間のパスをセグメント木などで扱える半開区間の集合に変換する。区間の数はO(log(|V|))個。
ひとつの区間は連結した頂点たちにIDをふったもので、頂点の深さは全て異なる。その区間内では、(深さの値の差)=(IDの値の差) になっている.
1クエリ O(log(|V|))
スタックオーバーフロー回避版
*/
class HLDecomposition {
    int cur = 0;
    void bfs(const vector<vector<int> > &G) {
        queue<tuple<int, int, int> > que;
        vector<int> order;
        que.push(make_tuple(0, -1, 0));
        while (!que.empty()) {
            int u, pre, d;
            tie(u, pre, d) = que.front();
            que.pop();
            parent[u] = pre;
            depth[u] = d;
            order.push_back(u);
            for (int v : G[u])if (v != pre) {
                que.push(make_tuple(v, u, d + 1));
            }
        }
        reverse(order.begin(), order.end());
        for (int u : order) {
            sub[u] = 1;
            for (int v : G[u])if (v != parent[u])sub[u] += sub[v];
        }
    }

    void dfs_stk(const vector<vector<int> > & G) {
        stack<pair<int, int> > stk;
        stk.push(make_pair(0, 0));
        while (!stk.empty()) {
            int u, h, pre;
            tie(u, h) = stk.top();
            stk.pop();
            head[u] = h;
            id[u] = cur++;
            pre = parent[u];
            int heavy = -1, maxi = 0;
            for (int v : G[u]) {
                if (v != pre && maxi < sub[v]) {
                    maxi = sub[v];
                    heavy = v;
                }
            }
            for (int v : G[u]) {
                if (v != pre&&v != heavy) {
                    stk.push(make_pair(v, v));
                }
            }
            if (heavy != -1)stk.push(make_pair(heavy, h));
        }
    }
public:
    vector<int> parent, depth, sub, id, head;
    
    HLDecomposition(const vector<vector<int> > &G) {
        parent = depth = sub = id = head = vector<int>(G.size());
        bfs(G);
        dfs_stk(G);
    }

    /*
    パス(u, v)を半開区間の集合に変換する。
    O(log(|V|))
    */
    vector<pair<int, int> > goUpToLCA(int u, int v) {
        vector<pair<int, int> > res;
        while (true) {
            if (head[u] == head[v]) {
                if (depth[u] > depth[v])swap(u, v);
                res.emplace_back(id[u], id[v] + 1);
                break;
            }
            else {
                if (depth[head[u]] > depth[head[v]])swap(u, v);
                res.emplace_back(id[head[v]], id[v] + 1);
                v = parent[head[v]];
            }
        }
        return res;
    }
};

int N, Q, K;
vector<vi> G;
int vs[300001], ans[300001];

int main() {
    scanf("%d", &N);
    G.resize(N);
    rep(i, N - 1) {
        int u, v;
        scanf("%d%d", &u, &v);
        // 0-indexedとする。
        --u;
        --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    HLDecomposition hld(G);
    // sgs[l]はlをheadとするセグメント[l, R)に対して
    // l<r<=R, r∈sgs[l]
    // を満たすような多重集合
    unordered_map<int, vi> sgs;

    scanf("%d", &Q);
    while (Q--) {
        sgs.clear();
        scanf("%d", &K);
        rep(i, K) {
            scanf("%d", &vs[i]);
            --vs[i];
            /*
            頂点vs[i]を含む部分木は
            vs[i], vs[i]の親、vs[i]の親の親、、、根
            つまりvs[i]の先祖すべてを根とする部分木すべて。
            これをすべて得るにはvs[i]から根までのパスを見るだけでいいが、
            O(|V|)かかる。
            かわりに、HL分解によってO(log|V|)個のパスを得る。
            */
            // log(|V|)個のパスに変換
            auto s = hld.goUpToLCA(0, vs[i]);
            each(p, s) {
                // ここが最も深い
                // O(log(N)ΣK)
                sgs[p.first].push_back(p.second);
            }
        }
        rep(i, K + 1)ans[i] = 0;

        each(p, sgs) {
            /*
            headのidをlとするようなパスについて考える。
            IDがlである頂点を根とする部分木は、黒い頂点をcn個含む。
            */
            int l = p.first, cn = sz(p.second);
            // rを昇順に見る。
            // より深い頂点へ向かっていく。
            sort(all(p.second));
            each(r, p.second) {
                /*
                r-1に対応する頂点が黒いので、
                rまで見たら黒色が1つ減る。
                [l, r)に対応するr-l個の頂点はcn個の黒い頂点を持つ。
                */
                ans[cn] += r - l;
                l = r;
                // 黒い頂点を1個減らす。(その黒い頂点よりも下へ行く)
                cn--;
            }
        }
        ans[0] = N;
        for (int i = 1; i <= K; ++i)ans[0] -= ans[i];
        rep(i, K + 1)printf("%d%c", ans[i], i != K ? ' ' : '\n');
    }
}
広告を非表示にする