C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題G (Game on Tree 2) を解いてみた.
■感想.
1. 問題G は, 方針が見えなかったので, 解説(プログラム)を参考に実装して, AC版に持って行く方針を取った.
2. 苦手な動的計画法(木dp)の訓練を積めたので, 非常に良かったと思う.
3. いったん自力で実装してみたものの, AC版に到達できなかった.
-> 原因としては, 二つの multiset の 個数調整で, 実装が正しくなかったこと, dpへの中央値設定(のタイミング, 更新条件)などがあげられると推測する.
いずれにしても, dfsの実装を正しく行うことは, 相変わらず, 直観的に分かりづらく, 難しく感じる(※)ため, 継続して, 今後の課題になっていくと思う.
※dfsの終了条件, dp更新(条件, タイミング)などが, 難しく感じる原因の一つと推測する.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 218 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題G/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 |
// 解答不能. // https://atcoder.jp/contests/abc218/editorial/2607 // -> dfs の 実装パターン を 暗記すること(特に, 終了条件, multiset の 利用方法など). // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; #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 int a[101010], dp[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); vvi G(N); rep(i, N - 1){ int u, v; scanf("%d %d", &u, &v); u--, v--; G[u].pb(v); G[v].pb(u); } // 2. 中央値. auto f = [&](multiset<int> &l, multiset<int> &r) -> int{ int m = -1; if(l.size() == r.size() + 1){ auto it = l.end(); m = *(--it); }else{ auto it1 = l.end(); auto it2 = r.begin(); m = (*(--it1) + *it2) / 2; } return m; }; // 3. 個数調整. auto g = [&](multiset<int> &l, multiset<int> &r) -> void{ // 左側の最大値を, 右側に移動. if(l.size()){ auto itr = l.end(); --itr; r.insert(*itr); l.erase(itr); } // 左側, 右側のサイズを調整. while(l.size() < r.size()){ l.insert(*r.begin()); r.erase(r.begin()); } return; }; // 4. 削除. auto h = [&](multiset<int> &l, multiset<int> &r, int x) -> void{ auto itr = l.end(); --itr; if(*itr < x) r.erase(r.lower_bound(x)); else l.erase(l.lower_bound(x)); return; }; // 5. dfs. multiset<int> l, r; auto dfs = [&](auto self, int cur, int bef, int d) -> void{ // 多重集合に, 要素を追加. l.insert(a[cur]); g(l, r); // dp更新. int mMin = 2020202020; int mMax = 0; for(int nex : G[cur]){ if(nex != bef){ self(self, nex, cur, d + 1); mMin = min(mMin, dp[nex]); mMax = max(mMax, dp[nex]); } } // 中央値設定など. if(mMax == 0) dp[cur] = f(l, r); else if(d & 1) dp[cur] = mMin; else dp[cur] = mMax; // 多重集合から, 要素を削除. h(l, r, a[cur]); g(l, r); // 終了. return; }; // 6. 木dp. dfs(dfs, 0, -1, 0); // 7. 出力. printf("%d\n", dp[0]); 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 |
[入力例] 5 2 4 6 8 10 4 5 3 4 1 5 2 4 [出力例] 7 ※AtCoderテストケースより [入力例] 5 6 4 6 10 8 1 4 1 2 1 5 1 3 [出力例] 8 ※AtCoderテストケースより [入力例] 6 2 2 6 4 6 6 1 2 2 3 4 6 2 5 2 6 [出力例] 2 ※AtCoderテストケースより [入力例] 2 6 18 1 2 [出力例] 12 [入力例] 3 6 8 2 1 2 2 3 [出力例] 6 [入力例] 6 6 2 8 12 4 2 1 2 1 6 6 3 6 4 4 5 [出力例] 5 [入力例] 16 8 2 10 12 16 2 4 20 18 14 12 6 4 8 10 6 1 2 1 3 2 4 2 5 4 8 4 9 5 10 5 11 3 6 3 7 6 12 6 13 7 14 7 15 7 16 [出力例] 10 [入力例] 9 18 2 4 18 24 12 8 14 12 1 2 1 3 2 4 2 5 5 6 5 7 7 8 7 9 [出力例] 15 |
■参照サイト
AtCoder Beginner Contest 218