C++の練習を兼ねて, AtCoder Beginner Contest 160 の 問題F (F – Distributing Integers) を解いてみた.
■感想.
1. 方針が全く分からなかったので, 解説を確認して, 実装したところ, 何とかAC版となった.
2. ただし, 木dp, 全方位木dp という馴染みのないものを実装することになったため, 非常に苦労したものの, 新しい知識が増えたので良かったと思う.
3. あと, 幅優先探索の復習も出来たので, 非常に良かったと思った.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 160 解説をご覧下さい.
■C++版プログラム(問題F／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 |
// コメント修正して再提出. #include <bits/stdc++.h> using namespace std; using LL = long long; using vvi = vector<vector<int>>; using P = pair<int, int>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back #define a first #define b second const LL MOD = 1e9 + 7; const int LIMIT = 202020; LL FAC[LIMIT], INV[LIMIT]; int d[LIMIT]; // 頂点 1 からの 距離 を 保存. int size[LIMIT]; // 木の大きさ. LL dp[LIMIT]; // 木dp. // グラフを幅優先探索する. // https://ja.wikipedia.org/wiki/幅優先探索 // ※bfsの動作確認用. // @param G: グラフ. // @param s: グラフの探索開始頂点. // @param d: 探索開始地点からの距離. // @return: 特に無し. void bfs(vvi &G, int s, int* d){ // 1. 空のキュー. queue<int> q; // 2. 訪問済みフラグ設定. // ※スタート地点は, 距離ゼロを指定. d[s] = 0; // 3. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 4. キューから取り出す. int u = q.front(); q.pop(); // 5. 取り出した要素を処理. for(auto &e : G[u]){ // 6. 訪問済であれば, 処理をスキップ. if(d[e] > 0) continue; if(d[e] == 0 && e != s) d[e] = d[u] + 1, q.push(e); } } return; } // Fermat's little theorem から, 大きな冪乗の計算を行う. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL mPow(LL a, LL b){ LL t = 1; while(b){ if(b & 1) t = (t * a) % MOD; a = a * a % MOD; b >>= 1; } return t % MOD; } int main(){ // 1. 入力情報. int N, a, b; scanf("%d", &N); vvi G(N); rep(i, N - 1){ scanf("%d %d", &a, &b); a--, b--; G[a].pb(b); G[b].pb(a); } // ※ 以下, 解説通り. // 2. 事前計算. FAC[0] = 1; repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD; rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2); rep(i, LIMIT) size[i] = 1, dp[i] = 1; // 3. 頂点 1 から 各頂点までの距離を計算. bfs(G, 0, d); // 4. 頂点 1 から 遠い順, 近い順 に並び替え. priority_queue<P> fPq; priority_queue<P, vector<P>, greater<P>> nPq; rep(i, N){ // {距離, 頂点番号} fPq.push({d[i], i}); nPq.push({d[i], i}); } // 5. 木dp. while(!fPq.empty()){ // 5-1. 頂点 v を一つ取り出す. P p = fPq.top(); fPq.pop(); // 5-2. 頂点 v の 頂点番号は？ int v = p.b; // 5-3. 頂点 v を 根とする部分木 の サイズ を 集計しながら, 木dp も 更新. for(auto &u : G[v]){ // 頂点 v の 子供 に 相当する頂点 u を 選択. if(d[u] > d[v]){ // 頂点 v の 周囲 の 頂点 u で, 頂点 1 から, より遠いものを加算. size[v] += size[u]; // 頂点 v の 周囲 の 頂点 u について, 木dp の 更新. dp[v] *= dp[u]; dp[v] %= MOD; dp[v] *= INV[size[u]]; dp[v] %= MOD; } } // 5-4. 頂点 v を 根とする部分木 の サイズ を 考慮し, 木dp を 更新. dp[v] *= FAC[size[v] - 1]; dp[v] %= MOD; } // 6. 全方位木dp. while(!nPq.empty()){ // 6-1. 頂点 u を一つ取り出す. P p = nPq.top(); nPq.pop(); // 6-2. 頂点 u の 頂点番号は？ int u = p.b; // 6-3. 頂点 u の 周囲の頂点 を見ながら, 自身(u) を 集計. LL dpu = dp[u]; for(auto &v : G[u]){ // もともと, 頂点 v が 頂点 u の 親頂点 である場合. if(d[u] > d[v]){ // 頂点 v の dp[v] を 再計算. dpu *= dp[v]; dpu %= MOD; // 頂点 u の 分 を 割り戻す. dpu *= mPow(dp[u], MOD - 2); dpu %= MOD; dpu *= FAC[size[u]]; dpu %= MOD; // 頂点 u の 子頂点 を 考慮. dpu *= INV[size[u] - 1]; dpu %= MOD; // 頂点 v が 子頂点 の 立場 になったので, 再計算. dpu *= INV[N - 1]; dpu %= MOD; dpu *= FAC[N - 1 - size[u]]; dpu %= MOD; // 頂点 u が 親になるので, 頂点 v が 子頂点 とした場合について 逆元 を 乗ずる. dpu *= FAC[N - 1]; dpu %= MOD; dpu *= INV[N - size[u]]; dpu %= MOD; } } // 6-4. 木dp の 更新. dp[u] = dpu; } // 7. 出力. rep(i, N) printf("%lld\n", dp[i]); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 |
[入力例] 3 1 2 1 3 [出力例] 2 1 1 ※AtCoderテストケースより [入力例] 2 1 2 [出力例] 1 1 ※AtCoderテストケースより [入力例] 5 1 2 2 3 3 4 3 5 [出力例] 2 8 12 3 3 ※AtCoderテストケースより [入力例] 8 1 2 2 3 3 4 3 5 3 6 6 7 6 8 [出力例] 40 280 840 120 120 504 72 72 ※AtCoderテストケースより [入力例] 11 1 2 2 4 2 5 1 3 3 6 7 6 6 8 8 9 8 10 8 11 [出力例] 7200 2700 12600 270 270 15120 1512 8640 864 864 864 [入力例] 11 3 2 2 4 2 5 1 3 1 6 7 6 6 8 8 9 8 10 8 11 [出力例] 12600 2700 7200 270 270 15120 1512 8640 864 864 864 [入力例] 30 1 2 1 3 5 1 4 1 6 2 2 7 2 8 6 9 6 10 7 11 8 12 8 13 3 14 4 19 4 20 14 15 14 18 15 16 15 17 5 21 5 22 22 23 22 24 22 30 23 25 23 26 23 27 25 28 25 29 [出力例] 627806444 840488480 156951611 625311831 258203730 982276504 488606323 982276504 930423334 930423334 740986430 930423334 930423334 431390325 381265594 875216061 875216061 876944500 504321101 504321101 733041513 539230173 384807545 742732080 931645289 185683020 185683020 687298118 687298118 742732080 |
■参照サイト
AtCoder Beginner Contest 160