C++の練習を兼ねて, AtCoder Beginner Contest 321 の 問題E (Complete Binary Tree) を解いてみた.
■感想.
1. 問題E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題E で, 完全二分木を復習が出来たので, 良かったとおもう.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 321 解説 の 各リンク を ご覧下さい.
■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 |
// C++20(GCC 12.2) #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 int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. 2 の 冪乗. vl cPow; cPow.pb(1LL); rep(i, 60) cPow.pb(cPow.back() << 1LL); // 3. 各テストケース. rep(i, T){ // 3-1. テストケース入力情報. LL N, X, K; scanf("%lld %lld %lld", &N, &X, &K); // 3-2. K が 大きい(2 の 60乗 = 1152921504606846976 > 1e18). if(K > (60 - 1) * 2){ puts("0"); continue; } // 3-3. 頂点 X から, 距離 k の 頂点数は？ LL ans = 0; int k = (int)K; LL cur = X, bef = -1; while(cur){ // 前回以前に, 頂点 1 に 到達済. if(k == -1){ ++ans; break; } // 前回以前に, 子頂点(左 or 右)をベースに, 確認済みか？ int f = 0; if(bef == cur * 2) f = 1; if(bef == cur * 2 + 1) f = 2; // 区間[l, r]. int d = 0; LL l = 0, r = 0; if(f == 0) l = cur; if(f == 1) l = cur * 2 + 1; if(f == 2) l = cur * 2; while(d < k && (l * 2) <= N){ ++d; l *= 2; } // 加算. if(d == k){ r = min(N, l + cPow[d] - 1); ans += r - l + 1; } // 親頂点へ移動. bef = cur; cur >>= 1; --k; // 親頂点へ移動したことが無い場合. if(f == 0) --k; } // 3-4. 出力. printf("%lld\n", ans); } 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 |
[入力例] 5 10 2 0 10 2 1 10 2 2 10 2 3 10 2 4 [出力例] 1 3 4 2 0 ※AtCoderテストケースより [入力例] 10 822981260158260522 52 20 760713016476190629 2314654 57 1312150450968417 1132551176249851 7 1000000000000000000 1083770654 79 234122432773361868 170290518806790 23 536187734191890310 61862 14 594688604155374934 53288633578 39 1000000000000000000 120160810 78 89013034180999835 14853481725739 94 463213054346948152 825589 73 [出力例] 1556480 140703128616960 8 17732923532771328 65536 24576 2147483640 33776997205278720 7881299347898368 27021597764222976 ※AtCoderテストケースより [入力例] 25 7 5 1 7 5 2 7 5 3 7 5 4 7 5 5 25 20 2 25 20 5 123 100 5 123 100 6 123 100 7 123 100 8 3300 25 6 3300 25 7 3300 25 8 20231112 12345 5 20231112 12345 8 20231112 12345 10 20231112 12345 12 20231112 12345 13 20231112 12345 15 202309232100 5555555 10 202309232100 5555555 13 202309232100 5555555 15 202309232100 5555555 18 202309232100 5555555 20 [出力例] 1 2 1 2 0 2 3 4 8 7 14 94 161 120 48 384 1536 2048 2048 4094 1536 12288 49152 65536 131072 |