C++の練習を兼ねて, AtCoder Grand Contest 035 の 問題C (Skolem XOR Tree) を解いてみた.
■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 035 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/agc035/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; 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 main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. 2の冪乗 を用意. vector<int> cPow2; set<int> stPow2; cPow2.pb(1); stPow2.insert(1); while(cPow2.back() < 1e5){ // 最大値を2倍. int p = 2 * cPow2.back(); // 保存. cPow2.pb(p); stPow2.insert(p); } // 3. N が 2の冪乗 である場合. if(stPow2.count(N)){ puts("No"); return 0; } // 4. 辺を保存(※解説通り). set<P> ans; ans.insert({1, 2}); ans.insert({2, 3}); ans.insert({3, N + 1}); ans.insert({N + 1, N + 2}); ans.insert({N + 2, N + 3}); repx(i, 4, N + 1){ if(i == N && !(N & 1)) break; if(i & 1){ ans.insert({N + 1, i}); ans.insert({i - 1, i}); }else{ ans.insert({N + 1, N + i}); ans.insert({N + i, N + i + 1}); } } // 5. N が 偶数の場合. if(!(N & 1)){ int mPow2 = 1; for(auto &p : cPow2){ if(p < N) mPow2 = p; else break; } int t = N ^ mPow2 ^ 1; if(!(t & 1)) t += N; ans.insert({t, N}); ans.insert({mPow2 + N, N * 2}); } // 6. 出力. puts("Yes"); for(auto &p: ans) printf("%d %d\n", p.a, p.b); 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 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 |
[入力例] 3 [出力例] Yes 1 2 2 3 3 4 4 5 5 6 ※AtCoderテストケースより [入力例] 1 [出力例] No ※AtCoderテストケースより [入力例] 5 [出力例] Yes 1 2 2 3 3 6 4 5 6 5 6 7 6 9 7 8 9 10 [入力例] 6 [出力例] Yes 1 2 2 3 3 6 3 7 4 5 7 5 7 8 7 10 8 9 10 11 10 12 [入力例] 7 [出力例] Yes 1 2 2 3 3 8 4 5 6 7 8 5 8 7 8 9 8 11 8 13 9 10 11 12 13 14 [入力例] 8 [出力例] No [入力例] 10 [出力例] Yes 1 2 2 3 3 10 3 11 4 5 6 7 8 9 11 5 11 7 11 9 11 12 11 14 11 16 11 18 12 13 14 15 16 17 18 19 18 20 [入力例] 12 [出力例] Yes 1 2 2 3 3 13 4 5 5 12 6 7 8 9 10 11 13 5 13 7 13 9 13 11 13 14 13 16 13 18 13 20 13 22 14 15 16 17 18 19 20 21 20 24 22 23 |
■参照サイト
AtCoder Grand Contest 035