C++の練習を兼ねて, AtCoder Regular Contest 083 の 問題E (Bichrome Tree) を解いてみた.
■感想.
1. E問題は, 方針が全く見えず, 解説を確認して, AC版に到達できたので, 良かったと思う.
2. 問題文で問われている内容を理解するのに, 時間かかってしまったように思う.
3. 木dp の 訓練, 幅優先探索の復習が出来たので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 083 解説 を ご覧下さい.
■C++版プログラム(問題E/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 |
// 解き直し. // https://img.atcoder.jp/arc083/editorial.pdf #include <bits/stdc++.h> using namespace std; 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 int d[1010]; // 頂点 1 からの 距離 を 保存. int x[1010]; // 重み(数列). int dpX[1010]; // 木dp(頂点 i を 根 とみた 部分木 で 同じ色). int dpY[1010]; // 木dp(頂点 i を 根 とみた 部分木 で 異なる色). // 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. 探索地点 s をキュー q に追加. q.push(s); // 3. キューが空になるまで繰り返し. while(!q.empty()){ // 4. 頂点を一つ取り出す. int u = q.front(); q.pop(); // 5. 隣接する頂点を確認. for(auto &e : G[u]){ // 6. 訪問済であれば, 処理をスキップ. if(d[e]) continue; if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e); } } return; } int main(){ // 1. 入力情報. int N, p; scanf("%d", &N); vvi G(N); repx(i, 1, N){ scanf("%d", &p); p--; G[i].pb(p); G[p].pb(i); } rep(i, N) scanf("%d", &x[i]); // 2. 頂点 1 から 各頂点までの距離を計算. bfs(G, 0, d); // rep(i, N) printf("%d ", d[i]); // puts(""); // 3. 頂点 1 から 遠い順 に並び替え. priority_queue<P> pq; rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号} // 4. 木dp. bool ok = true; while(!pq.empty()){ // 4-1. 頂点 v を一つ取り出す. P p = pq.top(); pq.pop(); // 4-2. 頂点 v の 頂点番号は? int v = p.b; // 4-3. 配列宣言. int z[5050], xy = 0, wSum = 0; memset(z, 0, sizeof(z)); // 4-4. スタート地点は, 1 を 設定. z[0] = 1; // 4-5. 頂点 v を 根とする部分木 について, 木dp を 更新. // printf("1. v=%d\n", v); for(auto &u : G[v]){ // 頂点 v の 子供 に 相当する頂点 u を 選択. if(d[u] > d[v]){ // 頂点 v の 子供について, 重みの総和 を 集計. xy += x[u]; // 頂点 u の 重み(※同じ色, 子孫). xy += dpY[u]; // 頂点 u の 重み(※異なる色, 子孫). // 頂点 v の 子供について, 重みの総和(最小値) を 集計. wSum += min(x[u], dpY[u]); // 頂点 v の 子供について, 同色のものの重みの和が, x[v]以下となるか? // Typical DP Contest (A - コンテスト) を ベース に 実装. // https://atcoder.jp/contests/tdpc/tasks/tdpc_contest repr(i, x[v], 0){ if(z[i]){ if(i + x[u] <= x[v]) z[i + x[u]] = 1; if(i + dpY[u] <= x[v]) z[i + dpY[u]] = 1; } // printf("2. u=%d dpX=%d dpY=%d\n", u, dpX[u], dpY[u]); } } } // 4-6. x[v]以下となる z[i] を 探索. int maxZ = 0; rep(i, x[v] + 1) if(z[i]) maxZ = i; // 4-7. 割り当てを行う. if(wSum <= x[v]){ dpX[v] = x[v] - maxZ; dpY[v] = xy + dpX[v] - x[v]; }else{ ok = false; break; } } // rep(i, N) printf("%d ", dpX[i]); // puts(""); // rep(i, N) printf("%d ", dpY[i]); // puts(""); // 5. 出力. printf("%s\n", ok ? "POSSIBLE" : "IMPOSSIBLE"); 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 |
[入力例] 3 1 1 4 3 2 [出力例] POSSIBLE ※AtCoderテストケースより [入力例] 3 1 2 1 2 3 [出力例] IMPOSSIBLE ※AtCoderテストケースより [入力例] 8 1 1 1 3 4 5 5 4 1 6 2 2 1 3 3 [出力例] POSSIBLE ※AtCoderテストケースより [入力例] 1 0 [出力例] POSSIBLE ※AtCoderテストケースより [入力例] 5 1 4 1 4 5 4 2 3 1 [出力例(debug版)] 1 4 2 0 1 3 0 0 0 0 POSSIBLE [入力例] 10 1 4 1 4 4 4 9 1 9 1 1 1 1 1 1 1 1 1 1 [出力例(debug版)] 0 1 1 0 1 1 1 1 0 1 0 0 0 3 0 0 0 0 1 0 IMPOSSIBLE [入力例] 11 7 8 1 8 8 1 1 4 4 7 10 2 3 6 2 5 2 7 3 6 1 [出力例(debug版)] 0 2 3 0 2 5 0 0 3 6 1 12 0 0 3 0 0 1 3 0 0 0 POSSIBLE [入力例] 15 1 1 1 4 4 5 5 6 6 6 3 3 12 12 12 3 5 1 3 8 1 2 5 3 1 4 2 3 2 [出力例(debug版)] 1 3 1 0 0 0 1 2 5 3 1 1 2 3 2 13 0 4 11 0 1 0 0 0 0 0 2 0 0 0 POSSIBLE |
■参照サイト
AtCoder Regular Contest 083