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'); } }
