C++の練習を兼ねて, AtCoder Regular Contest 084 の 問題D (Small Multiple)を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 01-BFS の 復習が出来たので良かったと思う.
3. 実装に苦労したものの, 個人的には, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 084 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/arc084/editorial.pdf // 01-BFSのちょっと丁寧な解説 // https://betrue12.hateblo.jp/entry/2018/12/08/000020 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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 pof pop_front #define pob pop_back #define pub push_back #define puf push_front const int INF = 2020202020; int d[101010]; int main(){ // 1. 入力情報. int K; scanf("%d", &K); // 2. 01-BFS(解説通り). // https://ja.wikipedia.org/wiki/幅優先探索 // -> 01-BFS版へ修正. auto bfs01 = [&](int s){ // 2-1. 空のキュー. deque<int> dq; // 2-2. 探索開始地点 s の コスト設定. d[s] = 0; // 2-3. 探索開始地点 s をキュー に追加. dq.pub(s); while(!dq.empty()){ // 2-4. キュー の 先頭要素を取り出す. int u = dq.front(); dq.pof(); // 2-5. コストを計算して, 小さい場合に, コストを更新. // コスト 0 における遷移(※コストの更新式で, +0 とする点に要注意). int u0 = u * 10 % K; // 10倍. if(d[u0] > d[u] + 0) d[u0] = d[u] + 0, dq.puf(u0); // コスト 1 における遷移. int u1 = (u + 1) % K; // 1加算. if(d[u1] > d[u] + 1) d[u1] = d[u] + 1, dq.pub(u1); } return; }; rep(i, 101010) d[i] = INF; bfs01(1); // 3. 出力. printf("%d", d[0] + 1); 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 |
[入力例] 6 [出力例] 3 ※AtCoderのテストケースより [入力例] 41 [出力例] 5 ※AtCoderのテストケースより [入力例] 79992 [出力例] 36 ※AtCoderのテストケースより [入力例] 2019 [出力例] 3 [入力例] 2020 [出力例] 2 [入力例] 2021 [出力例] 3 [入力例] 753 [出力例] 3 [入力例] 33333 [出力例] 15 |