C++の練習を兼ねて, AtCoder Regular Contest 087 の 問題E (Prefix-free Game) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 普段使わない自己参照構造体による実装だったため, 実装に苦労したものの, Trie木という新しい知識が増えたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 087 解説 を ご覧下さい.
■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 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 |
// 解き直し. // https://img.atcoder.jp/arc087/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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 struct Trie{ int d; // ノードまでの深さ. int c; // 子ノードの個数. int v; // 訪問済みフラグ. struct Trie *t[2]; // 子ノード. }; Trie *makeTrie(){ Trie *t = new Trie; t->d = 0; t->c = 0; t->v = 0; t->t[0] = NULL; t->t[1] = NULL; return t; } int main(){ // 1. 入力情報. int N; LL L; scanf("%d %lld", &N, &L); vector<string> s; Trie *root = makeTrie(); rep(i, N){ // 1-1. 入力情報保存. char c[101010]; scanf("%s", c); string t(c); s.pb(t); // 1-2. トライ木 を 一つ固定. Trie *cur = root; // 1-3. 固定したトライ木 に 子ノード追加. rep(j, t.size()){ // j文字目が, '0' の 場合. if(t[j] == '0'){ if(cur->t[0] == NULL){ Trie *nt = makeTrie(); cur->t[0] = nt; cur->c++; } cur = cur->t[0]; } // j文字目が, '1' の 場合. if(t[j] == '1'){ if(cur->t[1] == NULL){ Trie *nt = makeTrie(); cur->t[1] = nt; cur->c++; } cur = cur->t[1]; } // 深さ, 訪問済みフラグ を 設定. cur->d = j + 1; cur->v = 0; } } // Trie Test. // ex. // 5 10 // 0 // 01 // 101 // 1000 // 1001 // // root c=2 d=0 -> OK. // root->t[0] c=1 d=1 -> OK. // root->t[1] c=1 d=1 -> OK. // root->t[0]->t[1] c=0 d=2 -> OK. // root->t[1]->t[0] c=2 d=2 -> OK. // root->t[1]->t[0]->t[0] c=2 d=3 -> OK. // root->t[1]->t[0]->t[1] c=0 d=3 -> OK. // root->t[1]->t[0]->t[0]->t[0] c=0 d=4 -> OK. // root->t[1]->t[0]->t[0]->t[1] c=0 d=4 -> OK. // // printf("root c=%d d=%d\n", root->c, root->d); // printf("root->t[0] c=%d d=%d\n", root->t[0]->c, root->t[0]->d); // printf("root->t[1] c=%d d=%d\n", root->t[1]->c, root->t[1]->d); // printf("root->t[0]->t[1] c=%d d=%d\n", root->t[0]->t[1]->c, root->t[0]->t[1]->d); // printf("root->t[1]->t[0] c=%d d=%d\n", root->t[1]->t[0]->c, root->t[1]->t[0]->d); // printf("root->t[1]->t[0]->t[0] c=%d d=%d\n", root->t[1]->t[0]->t[0]->c, root->t[1]->t[0]->t[0]->d); // printf("root->t[1]->t[0]->t[1] c=%d d=%d\n", root->t[1]->t[0]->t[1]->c, root->t[1]->t[0]->t[1]->d); // printf("root->t[1]->t[0]->t[0]->t[0] c=%d d=%d\n", root->t[1]->t[0]->t[0]->t[0]->c, root->t[1]->t[0]->t[0]->t[0]->d); // printf("root->t[1]->t[0]->t[0]->t[1] c=%d d=%d\n", root->t[1]->t[0]->t[0]->t[1]->c, root->t[1]->t[0]->t[0]->t[1]->d); // 2. 初期状態の完全二分木. // ex. // 入力値が, 01010 だった場合は, 01011 が, 初期状態の完全二分木であるかを確認. vl level; for(auto &t : s){ // 2-1. トライ木 を 一つ固定. Trie *cur = root; // 2-2. 固定したトライ木 の 子ノードをチェック. int tl = t.size(); rep(i, tl){ if(t[i] == '0'){ // 訪問済みフラグの更新を行うこと. if(cur->c == 1 && cur->v == 0) level.pb(L - (LL)i), cur->v++; // 子ノードに移動. if(i < tl - 1) cur = cur->t[0]; } if(t[i] == '1'){ // 訪問済みフラグの更新を行うこと. if(cur->c == 1 && cur->v == 0) level.pb(L - (LL)i), cur->v++; // 子ノードに移動. if(i < tl - 1) cur = cur->t[1]; } } } // 3. Grundy数 の 総XOR を 計算. LL ans = 0; for(auto &l : level){ // 3-1. 2で最大何回割り切れるか. LL grundy = 1; while(l % grundy == 0) grundy <<= 1; if((grundy > 1) && (l % grundy != 0)) grundy >>= 1; // 3-2. XOR演算子. ans ^= grundy; } // 4. 出力. printf("%s\n", (ans == 0) ? "Bob" : "Alice"); 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 |
[入力例] 2 2 00 01 [出力例] Alice ※AtCoderのテストケースより [入力例] 2 2 00 11 [出力例] Bob ※AtCoderのテストケースより [入力例] 3 3 0 10 110 [出力例] Alice ※AtCoderのテストケースより [入力例] 2 1 0 1 [出力例] Bob ※AtCoderのテストケースより [入力例] 1 2 11 [出力例] Alice ※AtCoderのテストケースより [入力例] 2 3 101 11 [出力例] Bob ※AtCoderのテストケースより [入力例] 5 10 0 01 101 1000 1001 [出力例] Bob [入力例] 10 15 0 01 101 1000 1001 10011 101000 10101011 1000100000 10101010101 [出力例] Alice |
■参照サイト
AtCoder Regular Contest 087