C++の練習を兼ねて, AtCoder Regular Contest 162 の 問題C (Mex Game on Tree) を解いてみた.
■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 実装に苦労したものの, 個人的には, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 162 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C/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 |
// 解き直し. // https://atcoder.jp/contests/arc162/editorial/6380 // 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 main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. dfs. // https://ja.wikipedia.org/wiki/深さ優先探索 auto dfs = [](auto&& self, vvi &G, int cur, int bef, int N, int K, int* m, int* s, int* a, int* f, vvi &aCount) -> void { // 部分木サイズ(往路). ++s[cur]; // 終了条件. if(m[cur]) return; // 訪問済みフラグ. m[cur] = 1; // 隣接頂点. for(auto &nex : G[cur]){ if(nex == bef) continue; self(self, G, nex, cur, N, K, m, s, a, f, aCount); } // 部分木サイズ(復路). if(bef != -1) s[bef] += s[cur]; // 書き込まれた整数(復路で調整). if(a[cur] != -1) ++aCount[cur][a[cur]]; if(bef != -1) rep(i, N + 1) aCount[bef][i] += aCount[cur][i]; // f[cur] = K となりうるか? // 0 ~ K - 1 の 未使用個数(n), -1 の頂点数(m1) を 集計. int n = 0, m1 = 0; rep(i, N + 1){ if(i < K && !aCount[cur][i]) ++n; m1 += aCount[cur][i]; } m1 = s[cur] - m1; // 判定(K が 使用済でないことが大前提). bool alice = false; if(!aCount[cur][K]){ // 0 ~ K - 1 の 未使用個数 が 0個, かつ, -1 の頂点数 が 1個以下. if(n == 0 && m1 <= 1) alice = true; // 0 ~ K - 1 の 未使用個数 が 1個, かつ, -1 の頂点数 が 1個. if(n == 1 && m1 == 1) alice = true; } // 保存. f[cur] = alice; }; // 3. テストケース. rep(i, T){ // 3-1. 各テストケース. int N, K; scanf("%d %d", &N, &K); vvi G(N); repx(j, 1, N){ int p; scanf("%d", &p); --p; G[p].pb(j); G[j].pb(p); } int a[N]; rep(j, N) scanf("%d", &a[j]); // 3-2. 部分木. int subTree[N], memo[N], f[N]; vvi aCount(N, vi(N + 1, 0)); rep(j, N) subTree[j] = memo[j] = f[j] = 0; dfs(dfs, G, 0, -1, N, K, memo, subTree, a, f, aCount); // rep(j, N) printf("f[%d]=%d\n", j, f[j]); // 3-3. f[v] = K が 存在するか? bool ok = false; rep(j, N) if(f[j]) ok = true; // 3-4. 出力. printf("%s\n", ok ? "Alice" : "Bob"); } 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 |
[入力例] 2 4 2 1 1 2 -1 -1 3 1 6 4 1 2 2 1 3 -1 -1 -1 -1 -1 -1 [出力例] Alice Bob ※AtCoderのテストケースより [入力例] 5 5 3 1 1 3 3 1 0 -1 2 0 7 4 1 1 2 2 3 3 0 0 -1 2 2 -1 -1 11 5 1 2 3 3 2 1 7 7 9 9 0 1 -1 2 3 4 -1 2 -1 4 5 9 4 1 1 1 1 3 3 4 5 1 0 3 3 -1 0 0 -1 2 20 5 1 1 2 2 3 3 5 5 6 6 7 7 8 8 10 10 11 11 13 -1 0 4 1 2 0 1 3 -1 -1 1 3 0 2 1 2 3 1 2 3 [出力例] Alice Bob Alice Bob Alice |
■参照サイト
AtCoder Regular Contest 162