C++の練習を兼ねて, AtCoder Beginner Contest 235 の 問題D (Multiply and Rotate) を解いてみた.
■感想.
1. 問題Dは, とりあえず実装したものの, AC版に到達できず, 解説プログラムを参考に, 修正版で, AC版に到達できたと思う.
2. 幅優先探索(応用版, グラフの頂点数削減)の復習が出来たので, 非常に良かったと思う.
3. 実装に苦労した箇所は, プログラム上に記載した T1 ～ T4 になるが, 個人的には, 落とし穴が, たくさんある印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 235 解説 を ご覧下さい.
■C++版プログラム(問題D／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 |
// 解き直し. // https://atcoder.jp/contests/abc235/editorial/3255 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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 pob pop_back #define pub push_back #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int a, N; scanf("%d %d", &a, &N); // 2. 10 の 冪乗. int M = 1; while(M <= N) M *= 10; // 3. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](int s, int* d){ // 空のキュー. queue<int> q; // 距離を設定. d[s] = 0; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. LL cx = (LL)q.front(); q.pop(); // Nの桁数 プラス 1 以上になった場合, Skip. if(cx >= M) continue; // x を 消して, x * a を 書き込む. LL nx1 = cx * a; if(nx1 < M && d[(int)nx1] == -1){ d[(int)nx1] = d[cx] + 1; q.push((int)nx1); } // x を 文字列と見做して, 末尾を先頭に移動. if(cx >= 10 && cx % 10 != 0){ string sx = to_string(cx), snx; snx.pub(sx.back()); sx.pob(); reverse(all(sx)); while(!sx.empty()){ snx.pub(sx.back()); sx.pob(); } if(!snx.empty()){ LL nx2 = stoll(snx); if(nx2 < M && d[(int)nx2] == -1){ d[(int)nx2] = d[cx] + 1; q.push((int)nx2); } } } } }; // [課題] // T1. 01_a_eq_2_00.txt などで, TLE版 となったため, ロジック修正が必要. // -> 解説プログラムを参考に, map<LL, int> を 廃止し, 配列を使用する形に修正(OK). // T2. Runtime Error となる件に対応するため, 配列サイズを, かなり大きめに設定(OK). // T3. 03_random_00.txt などの Runtime Error を 防止するため, long long型 を 部分的 に 廃止(OK). // -> ex. d[(int)nx1] == -1 の ような実装に修正. // T4. bfs の 判定を, nx1 <= M, nx2 <= M から nx1 < M, nx2 < M に 修正(OK). int d[M * 10 + 1]; rep(i, M * 10 + 1) d[i] = -1; bfs(1, d); // 4. 出力. printf("%d\n", d[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 |
[入力例] 3 72 [出力例] 4 ※AtCoderテストケースより [入力例] 2 5 [出力例] -1 ※AtCoderテストケースより [入力例] 2 611 [出力例] 12 ※AtCoderテストケースより [入力例] 2 767090 [出力例] 111 ※AtCoderテストケースより [入力例] 10 1000000 [出力例] 6 [入力例] 7 826630 [出力例] 11 [入力例] 5 320000 [出力例] 8 [入力例] 2 162578 [出力例] 17 [入力例] 3 768690 [出力例] 19 [入力例] 2 522086 [出力例] 19 |