C++の練習を兼ねて, AtCoder Beginner Contest 027 の 問題C (C – 倍々ゲーム) を解いてみた.
■感想.
1. 非常に苦労したものの, 試行錯誤から, 規則性を抽出できたので, AC版 と なった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 027解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, 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 #define a first #define b second const int MAX = 63; LL pow2[MAX]; int main(){ // 1. 入力情報. LL N; scanf("%lld", &N); // 2. 2 の 冪乗 を 保存. pow2[0] = 1; rep(i, MAX) pow2[i + 1] = pow2[i] << 1; // rep(i, MAX) printf("%lld\n", pow2[i]); // 3. 青木君勝利する区間を保存. // 以下の区間を予想. // [1, 1] // [6, 9] // [26, 41] // [106, 109] // ... // [as, ae] と 置いたとき, // ae = -1 + (2 の 1乗) + (2 の 3乗) + (2 の 5乗) + ... // as = ae - (2 の 偶数乗) + 1 // と仮定? // // (2 の 60乗) … 1152921504606846976 vector<P> v; LL as = 0, ae = -1; repex(i, 1, MAX, 2){ ae = ae + pow2[i]; as = ae - pow2[i - 1] + 1; v.pb({as, ae}); } // rep(i, v.size()) printf("%lld %lld\n", v[i].a, v[i].b); // 4. 判定. bool aoki = false; rep(i, v.size()){ if(N >= v[i].a && N <= v[i].b){ aoki = true; break; } } // 5. 出力. printf("%s\n", aoki ? "Aoki" : "Takahashi"); 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 |
[入力例] 1 [出力例] Aoki ※AtCoderテストケースより [入力例] 5 [出力例] Takahashi ※AtCoderテストケースより [入力例] 7 [出力例] Aoki ※AtCoderテストケースより [入力例] 10 [出力例] Takahashi ※AtCoderテストケースより [入力例] 123456789123456789 [出力例] Aoki ※AtCoderテストケースより [入力例] 25 [出力例] Takahashi [入力例] 123 [出力例] Aoki [入力例] 10921 [出力例] Aoki [入力例] 10922 [出力例] Takahashi [入力例] 111848105 [出力例] Takahashi [入力例] 111848106 [出力例] Aoki [入力例] 987654321987654321 [出力例] Takahashi [入力例] 3012345678901234567 [出力例] Aoki |
■参照サイト
AtCoder Beginner Contest 027