C++の練習を兼ねて, Educational DP Contest / DP まとめコンテスト の 問題P (P – Independent Set) を解いてみた.
■感想.
1. どこかで類題を見た記憶があったので, 探したところ, AtCoder Beginner Contest 036(D – 塗り絵) に似ていることが分かった.
2. 差分は, N = 1 を 含める(本問)か, 含めないか のようだった.
■C++版プログラム(問題P／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 |
// 下記を, 一部修正. // 解き直し. // ABC #036 解説. // http://abc036.contest.atcoder.jp/data/abc/036/editorial.pdf #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) typedef long long LL; const int LIMIT = 100000; const LL MOD = 1e9 + 7; struct edge { int to; // 次の頂点. int cost; // コスト. }; struct vertex { int id; // 頂点番号. int distance; // 指定された頂点(根)からの距離. }; int depth[LIMIT]; vector<edge> tree[LIMIT]; // AtCoder Beginner Contest 070 (問題D Transit Tree Path) を参照. // https://img.atcoder.jp/abc070/editorial.pdf // 深さ優先探索(depth-first search). // @param c: 探索地点となる頂点. // @param b: 探索地点から見て, 前回探索済の頂点. // @param d: 探索開始地点からの距離. // @return : 特に無し. void dfs(int c, int b, int d) { depth[c] = d; for (auto &e : tree[c]) { if (e.to == b) continue; dfs(e.to, c, d + e.cost); } } int main() { // 1. 入力情報取得. int N; cin >> N; map<int, int> m; // 開始頂点取得用. FOR(i, 0, N - 1) { int a, b; cin >> a >> b; a--, b--; tree[a].push_back({b, 1}); tree[b].push_back({a, 1}); m[a]++; m[b]++; } // 2. N = 1 の 場合は, 終了(※本問用で追加). if(N == 1){ cout << 2 << endl; return 0; } // 3. 探索開始の頂点(根)を取得し, 各頂点までの最短距離を保存. int root = -1; for(auto &p : m) { if(p.second == 1) { root = p.first; break; } } dfs(root, -1, 0); // cout << "root=" << root << endl; // FOR(i, 0, N) for(auto &p : tree[i]) cout << "i=" << i << " to=" << p.to << endl; // FOR(i, 0, N) cout << depth[i] << " "; // 4. 解説通り(色の塗り方の数をカウント). // -> tree DP を 使って解くとのこと. // 探索開始の頂点(根) から遠い順に, f, g の 値を計算していく. // 4-1. 頂点と距離のセットで保管. vector<vertex> vertexes; FOR(i, 0, N) { vertex v; v.id = i; v.distance = depth[i]; vertexes.push_back(v); } // 4-2. 距離で, 降順sort. sort(vertexes.begin(), vertexes.end(), [](const vertex& x, const vertex& y) {return x.distance > y.distance;}); // 4-3. f, g を 帰納的に計算. LL f[N] = {}; LL g[N] = {}; for(auto &x : vertexes) { // 頂点 x を 親とする部分木で, x と 隣り合っている頂点(xの子)を探索. int p = x.id; // 親の頂点番号. LL lf = 1LL; LL lg = 1LL; // 隣接している, かつ, 探索開始の頂点(根) からより遠い場合は, xの子 と識別. for(auto &v : tree[p]) { int c = v.to; // 子の候補となる頂点番号. if(depth[p] < depth[c]) { lg *= f[c]; lf *= g[c]; lg %= MOD; lf %= MOD; } } // f, g を 更新. lf += lg; lf %= MOD; f[p] = lf; g[p] = lg; } // FOR(i, 0, N) cout << f[i] << " "; // cout << endl; // FOR(i, 0, N) cout << g[i] << " "; // 5. 出力 ～ 後処理. LL ans = f[root]; cout << ans << endl; return 0; } |
■参照サイト
Educational DP Contest / DP まとめコンテスト
AtCoder Beginner Contest 036 (D – 塗り絵)