C++の練習を兼ねて, 第七回 アルゴリズム実技検定 の 問題G (べき表現) を解いてみた.
■感想.
1. 問題Gは, 方針が見えなかったので, 解説の漸化式を参考の上, AC版に到達できた.
2. 個人的には, 深さ優先探索の訓練を積めたので, 理解を深めることが出来たと思う.
3. 解説にある漸化式を実装すると, 数列内に重複要素が出てこないことが, 非常に不思議な印象を受けた.
※ 解説を見る前は, 数列内の重複要素を排除する方法が分からなかったため.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト 第七回 アルゴリズム実技検定 の 各リンク を ご覧下さい.
■C++版プログラム(問題G／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 |
// 解き直し. // https://atcoder.jp/contests/past202107-open/editorial/1826 // 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 int main(){ // 1. 入力情報. LL N; scanf("%lld", &N); // 2. dfs(解説通り). // https://ja.wikipedia.org/wiki/深さ優先探索 auto dfs = [&](auto&& self, LL x) -> vl{ // 2-1. x が 0. vl ret = {}; if(x == 0) return ret; // 2-2. x = 0 (mod 3). if(x % 3 == 0){ ret = self(self, x / 3); for(auto &x : ret) x *= 3; } // 2-3. x = 1 (mod 3). if(x % 3 == 1){ ret = self(self, (x - 1) / 3); for(auto &x : ret) x *= 3; ret.pb(1); } // 2-4. x = 2 (mod 3). if(x % 3 == 2){ ret = self(self, (x + 1) / 3); for(auto &x : ret) x *= 3; ret.pb(-1); } // 2-5. 返却. return ret; }; vl ans = dfs(dfs, N); // 3. 出力. int M = ans.size(); printf("%d\n", M); rep(i, M) printf("%lld%s", ans[i], (i < M - 1) ? " " : "\n"); 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 |
[入力例] 6 [出力例] 2 9 -3 ※AtCoderのテストケースより [入力例] 9193 [出力例] 9 2187 27 1 -243 3 9 -81 6561 729 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 9 6561 2187 729 -243 -81 27 9 3 1 [入力例] 10120190919012 [出力例] 16 -1594323 9 -177147 -531441 1162261467 -4782969 387420489 -6561 -2187 2541865828329 -27 7625597484987 3486784401 10460353203 -94143178827 31381059609 ※但し, 上記のプログラムでは, 以下の内容が出力される. 16 7625597484987 2541865828329 -94143178827 31381059609 10460353203 3486784401 1162261467 387420489 -4782969 -1594323 -531441 -177147 -6561 -2187 -27 9 [入力例] 5 [出力例] 3 9 -3 -1 [入力例] 111 [出力例] 3 81 27 3 [入力例] 2022 [出力例] 4 2187 -243 81 -3 [入力例] 20220115 [出力例] 11 14348907 4782969 1594323 -531441 19683 6561 -729 -243 81 3 1 [入力例] 202107031300 [出力例] 14 282429536481 -94143178827 10460353203 3486784401 -129140163 4782969 -1594323 -531441 19683 -729 81 -27 -9 1 [入力例] 314159265358979 [出力例] 23 617673396283947 -205891132094649 -68630377364883 -22876792454961 -7625597484987 2541865828329 -847288609443 -282429536481 94143178827 3486784401 -14348907 4782969 531441 -177147 59049 -19683 2187 -729 -243 -81 27 -3 -1 |
■参照サイト
第七回 アルゴリズム実技検定