CS Academy Uniform Trees
リンク : https://csacademy.com/contest/archive/task/uniform-trees/statement/
問題概要
N頂点の木が与えられる、それそれの頂点にラベルがつけられる。以下の条件を満たす頂点集合の通り数を求めよ。
・頂点集合のうちある１つの頂点はほかのすべての頂点の祖先となる。これを根とする。
・根以外の頂点は頂点集合中の最も近い祖先とつなぐ。
解説
dp[i][j]を頂点iの子孫の頂点集合に関して、つながれた祖先からの頂点がjのラベルをつけられた働きをするときの通り数とすると、dp[i][j]=∏{(x∈child(i))dp[x][j]+1}-1となる。このdpはi<=2×、j<=2×
、となるため、静的に確保してしまうと、MLEする。そこでjに関しては中身が0のことが多いため、mapでもっておくことを考える。すると、子孫からのdpをうけとるときにマージテクなるものをつかうことができる。これは大きいほうに小さいものを入れることを繰り返せば
からNlogNに落とせるといったテクニックである。
メモ:マージテクは計算量空間量ともに削減する。
LL n, ans, a[210000],dp[210000]; map<LL, LL>mp[210000]; vector<vector<LL>>g; void merge(LL a, LL b) { if (mp[a].size() < mp[b].size()) { swap(mp[a], mp[b]); swap(dp[a], dp[b]); } for (auto it = mp[b].begin(); it != mp[b].end(); it++) { if (mp[a].count(it->first)) { (dp[a] += (mp[a][it->first] *( it->second - 1 + MOD)) % MOD) %= MOD; mp[a][it->first] = (mp[a][it->first] * it->second) % MOD; } else { (dp[a] += it->second)%=MOD; mp[a][it->first] = it->second; } } } void dfs(LL cur, LL par) { rep(i, g[cur].size()) { LL v = g[cur][i]; if (v == par)continue; dfs(v, cur); merge(cur, v); } LL num = (1 + dp[cur] + MOD - mp[cur].size()) % MOD; (ans += num) %= MOD; if (mp[cur].count(a[cur])) { (dp[cur] += num) %= MOD; (mp[cur][a[cur]] += num) %= MOD; } else { (dp[cur] += num+1) %= MOD; (mp[cur][a[cur]] += num+1) %= MOD; } } int main() { cin >> n; g.resize(n); rep(i, n) { LL x, y; cin >> x >> a[i]; x--; if (i) { g[x].push_back(i); g[i].push_back(x); } } dfs(0, -1); cout << ans << endl; return 0; }
CS Academy Wrong Brackets
リンク : https://csacademy.com/contest/archive/task/wrong-brackets/statement/
問題概要
( がN個、) がN個の文字列で、括弧の対応が正しくない文字列の中で辞書順でK番目を求めよ。
解説
辞書順より前から求めることを考える。次に ( か ) のどっちを置くか考えるとき、
まだ正しい括弧列になりうる場合
次が ( のときの全通りより、次が ) の場合のほうが大きいため 次が ( であり、後ろが正しくない括弧列の通り数とKのどちらが大きいか毎回比べると最終的な括弧列が求められる。
すでに正しくないことが確定した場合
残っているときは後ろが正しい括弧列でもいいため、コンビネーションを使って次が ( であり、後ろが何でもよいときの通り数とKを比べる。
方針ミス+初期化ミスで地獄見た...
LL n, k, C[100][100],dp[100][100]; LL func(int p, int q) { if (dp[p][q] != -1)return dp[p][q]; if (q == 0)return dp[p][q] = 1; if (p == 0)return dp[p][q] = 0; if (q < p)return 0; if (p == q)return dp[p][q] = C[p * 2][p - 1]; return dp[p][q] = func(p - 1, q) + func(p, q - 1); } int main() { string str = ""; cin >> n >> k; rep(i, n * 2 + 1) C[i][0] = C[i][i] = 1; for (int i = 1; i <= n * 2; i++) for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]); rep(i, 100)rep(j, 100)dp[i][j] = -1; dp[0][0] = 0; int p = n, q = n; bool ng = 0; while (p != 0 && q != 0) { if (p > q)ng = 1; if (ng) { if (C[p + q - 1][p - 1] < k) { k -= C[p + q - 1][p - 1]; cout << ")"; q--; } else { cout << "("; p--; } } else { if (func(p - 1, q) < k) { k -= func(p - 1, q); cout << ")"; q--; } else { cout << "("; p--; } } } while (p)cout << "(", p--; while (q)cout << ")", q--; cout << endl; return 0; }
CS Academy Ultimate Orbs
リンク : https://csacademy.com/contest/archive/task/ultimateorbs/statement/
問題概要
N個のオーブがある。それぞれのオーブは隣のオーブが自身のコスト+D以下だと、隣のオーブの重さを吸収する。それぞれのオーブに関して、自身が最後まで残ることができるかどうか調べよ。
解説
とりあえず、重さが最大のオーブは必ず残ることができる。あるオーブiから初めて、最大のオーブを吸収することができれば最後まで残ることができる。さらにこのオーブiを吸収できれば...と続けていけば、すべて求めることできる。flag[i]を最後になれるかどうかだとする。重さが最大の場合は1に初期化しておく。ではどのように探索すればよいか考える。オーブiから見ていって、自身より重い最寄りのオーブに関して考える。手前のものをL[i]、奥のものをR[i]とする。(L[i],R[i])の和+DがL[i]、R[i]の重さより重ければL[i]、R[i]から始めることができる。そうでない場合は始められない。このように探索していくと、それぞれのオーブについて1回しか探索しないことになる。そうすることによってO(N)で解ける。
再帰的に考える発想は難しい・・・
LL n, d, L[1100000], R[1100000], flag[1100000],sum[1100000], cnt; Pll a[1100000]; bool func(int cur) { bool ret = 0; if (cur == -1 || cur == n)return 0; if (flag[cur] != -1)return flag[cur] == 1 ? 1 : 0; if (L[cur] == -1 && R[cur] == n)return flag[cur] = 1; LL num = sum[R[cur]] - sum[L[cur]+1] + d; if (num >= a[L[cur]].fir)ret |= func(L[cur]); if (num >= a[R[cur]].fir)ret |= func(R[cur]); return flag[cur] = ret; } int main() { cin >> n >> d; rep(i, n) { cin >> a[i].fir; a[i].sec = i; sum[i + 1] += sum[i] + a[i].fir; flag[i] = -1; } vector<Pll>vec; vec.push_back(Pll(INF, -1)); rep(i, n) { while (vec.back().fir <= a[i].fir)vec.pop_back(); L[i] = vec.back().sec; vec.push_back(a[i]); } vec.clear(); vec.push_back(Pll(INF, n)); Rrep(i, n) { while (vec.back().fir <= a[i].fir)vec.pop_back(); R[i] = vec.back().sec; vec.push_back(a[i]); } rep(i, n) { if (func(i)) { if (cnt)cout << " "; cout << i + 1; cnt++; } } cout << endl; return 0; }
CS Academy Random Nim Generator
リンク : https://csacademy.com/contest/archive/task/random_nim_generator/statement/
問題概要
N個の0より大きくK以下の数字の入った配列を作ります。作った配列のすべてをxorすると0より大きくなるものは何通りあるか求めよ。
解説
まず、普通にdpをしてみようと考える。dp[i][j]をi番目の配列までのxorがjの通り数とする。すると
dp[i+1][j]=sum{{k=0,1,....K}{l=0,1,...K}if(kl==j)dp[i][k]}となる。しかしこれではO(NK3)となり到底間に合わない。そこでアダマール変換をする。アダマール変換とは、簡単に説明すると、C[i] = sum{jk=i} A[j]B[k] をO(NlogN)でやるものである。これを用いると、O(NKlogK)となる。これでもまだ足りない。ここで、アダマール変換は毎回同じことをしているかつ結合法則が成り立つため、繰り返し二乗法のようにアダマール変換をする。するとO(logNK*logK)となり間に合う。
namespace FWT { LL mod = MOD; void init(LL _mod) { mod = _mod; } LL modpow(LL a, LL n = mod - 2) { LL r = 1; while (n) r = r * ((n % 2) ? a : 1) % mod, a = a * a%mod, n >>= 1; return r; } void FWT(vector<LL>&a) { int n = a.size(); for (int d = 1; d < n; d <<= 1) for (int m = d << 1, i = 0; i < n; i += m) for (int j = 0; j < d; j++) { LL x = a[i + j], y = a[i + j + d]; a[i + j] = (x + y) % mod, a[i + j + d] = (x - y + mod) % mod; } } void UFWT(vector<LL>&a) { int n = a.size(); LL rev = modpow(2); for (int d = 1; d < n; d <<= 1) for (int m = d << 1, i = 0; i < n; i += m) for (int j = 0; j < d; j++) { LL x = a[i + j], y = a[i + j + d]; a[i + j] = 1LL * (x + y)*rev%mod, a[i + j + d] = (1LL * (x - y + mod)%mod*rev) % mod; } } vector<LL> solve(vector<LL>&a, vector<LL>b){ int n = a.size(); FWT(a); FWT(b); for (int i = 0; i<n; i++) a[i] = 1LL * a[i] * b[i] % mod; UFWT(a); return a; } }; LL n, k,ans; vector<LL>dp, ret; int main() { cin >> n >> k; FWT::init(30011); dp.resize(1 << 16); ret.resize(1 << 16); rep(i, k + 1)dp[i] = 1; ret[0] = 1; while (n > 0) { if (n & 1) { FWT::solve(ret, dp); } FWT::solve(dp, dp); n >>= 1; } rep(i, 1 << 16) if(i) ans += ret[i]; cout << ans%30011 << endl; return 0; }
CS Academy Connected Tree Subgraphs
リンク : https://csacademy.com/contest/archive/task/connected-tree-subgraphs/statement/
問題概要
N頂点の木が与えられる。それぞれの頂点に新たにラベル(頂点番号)をつける。1<=k<=Nのすべてのkについて、ラベルが1からkまでの頂点を選んだとき、1からkの頂点のみを含む部分グラフが存在する。この条件を満たす、ラベルの張り方の通り数を求めよ。
解説
考察をする。条件を言い換えると、根を1としたときに、1とつながる頂点から一つ選び2とラベルをつける。次に1,2とつながる頂点から一つ選び3とラベルをつける。......という風にラベルをつけていく通り数を求めることと同値である。次にこの考え方をした場合の数え方について考える。
上図の場合、1の部分を根とする。1は必ず最初に置く。次に2から下の並べ方を考える。すると2通りである。3についても同様。ここから全体の並べ方を求めようと考える。すると赤の部分と青の部分のみ考慮した並べ方は6C3である。そして赤の中での並べ方、青の中での並べ方について考慮すると、6C3×2×2=80 となる。
この例から、dp1[v]を自身より下の並べ方の通り数とし、vの頂点を根とするときの部分木の大きさをsub[v]とし、vとつながる頂点をe[i]と置く。すると、dp[v]は(sub[v]-1)Csub[e[1]]×(sub[v]-sub[e[1]]-1)C(sub[e[2]])....(sub[v]-sub[e[1]]-sub[e[2]]...sub[e[m-1]]-1)Csub[e[m]]×dp[e[1]]×dp[e[2]]....×dp[e[m]]となる。ここで、コンビネーションの部分を簡単にすると(sub[v]-1)!/(sub[e[1]]!×sub[e[2]]!×...sub[e[m]]!)となる。これで階乗とその逆元のみ用意すればよくなり実装が少し楽になる。
これで根が決まったときの問題は解けた。が全頂点を根として計算したい。そこで全方位木dpをおこなう。ここまでくればそこまで難しい全方位木dpではないため説明は省略する。
これを初見で解けたのはとてもうれしい。
LL n, sub[110000], dp1[110000], dp2[110000], ans, mfact[110000], rfact[110000]; vector<vector<LL>>g; int64_t pow(int64_t x, int64_t n) { int64_t ret = 1; while (n > 0) { if (n & 1) (ret *= x) %= MOD; (x *= x) %= MOD; n >>= 1; } return (ret); } int64_t inv(int64_t x) { return (pow(x, MOD - 2)); } void init() { mfact[0] = 1; for (int i = 1; i < 100002; i++) { mfact[i] = mfact[i - 1] * i % MOD; } rfact[100001] = inv(mfact[100001]); for (int i = 100001 - 1; i >= 0; i--) { rfact[i] = rfact[i + 1] * (i + 1) % MOD; } } void dfs1(LL cur, LL par) { LL sum = 0, ret = 1; rep(i, g[cur].size()) { LL v = g[cur][i]; if (v == par)continue; dfs1(v, cur); sum += sub[v]; } ret *= mfact[sum]; rep(i, g[cur].size()) { LL v = g[cur][i]; if (v == par)continue; ret *= rfact[sub[v]]; ret %= MOD; ret *= dp1[v]; ret %= MOD; } dp1[cur] = ret; sub[cur] = sum + 1; } void dfs2(LL cur, LL par, LL p) { LL sum = 0, rfacts = 1, ret = 1, memo = p; vector<LL>d(g[cur].size(), 1); ret *= p; ret %= MOD; ret *= mfact[n - 1]; ret %= MOD; rep(i, g[cur].size()) { LL v = g[cur][i]; if (v == par)continue; sum += sub[v]; ret *= rfact[sub[v]]; ret %= MOD; ret *= dp1[v]; ret %= MOD; rfacts *= rfact[sub[v]]; rfacts %= MOD; d[i] *= memo; d[i] %= MOD; memo *= dp1[v]; memo %= MOD; } ret *= rfact[n - sum - 1]; ret %= MOD; rfacts *= rfact[n - sum - 1]; rfacts %= MOD; dp2[cur] = ret; memo = 1; Rrep(i, g[cur].size()) { LL v = g[cur][i]; if (v == par)continue; d[i] *= memo; d[i] %= MOD; memo *= dp1[v]; memo %= MOD; } rep(i, g[cur].size()) { LL v = g[cur][i]; if (v == par)continue; LL nex = rfacts * mfact[sub[v]]; nex %= MOD; nex *= mfact[n - sub[v] - 1]; nex %= MOD; nex *= d[i]; nex%= MOD; dfs2(v, cur, nex); } } int main() { cin >> n; g.resize(n); init(); rep(i, n-1) { LL x, y; cin >> x >> y; x--, y--; g[x].push_back(y); g[y].push_back(x); } dfs1(0, -1); dfs2(0, -1, 1); rep(i, n) ans += dp2[i], ans %= MOD; cout << ans << endl; return 0; }
CS Academy Partial Ladder Graph
リンク : https://csacademy.com/contest/archive/task/partial_ladder_graph/statement/
問題概要
N2頂点とN+2(N-1)辺のグラフが与えられる。1<=i<=N-1 の頂点iはi+1同士を結んでいる。N<=i<=2N-1も同様である。また、1<=i<=N-1の頂点iと頂点i+(N-1)は結ばれている。このとき、辺を削除しても連結である、辺の集合の通り数を求めよ。
解説
Nが1から2に変わったときに、辺1-2、辺2-4、辺3-4の3辺のみしか変わらないため、一つ前の遷移が使えるのではという考察と、N<=から繰り返し二乗法か行列累乗が浮かぶ。そこでdp[i][0]をi番目までで、これからの遷移によっては連結になりうる通り数(現在は連結でない)とし、dp[i][1]をi番目までで、現在連結である通り数とする。そうすると、公式解説の図のように考えると、
dp[i+1][0]=dp[i][0]+dp[i][1]×2
dp[i+1][1]=dp[i][0]+dp[i][1]×4
となる。普通に計算してしまうとTLEである。この形なら行列累乗ができるため、O(log N)でこの問題が解ける。
LL n; int main() { cin >> n; n--; matrix<LL>mat(2), A(2,1); A.mat[0][0] = 1; A.mat[1][0] = 1; mat.mat[0][0] = 1; mat.mat[0][1] = 2; mat.mat[1][0] = 1; mat.mat[1][1] = 4; matrix<LL>ANS(mat.Pow(n)*A); cout << ANS.mat[1][0] << endl; return 0; }
