C++の練習を兼ねて, AtCoder Beginner Contest 161 の 問題D (D – Lunlun Number) を解いてみた(二回目).
■感想.
1. 前回版が, いまいちな実装だったので, 解説を見て, 解き直した.
※ Queue が 使えることが見えなかったので, 非常に勉強になったと思う.
2. 実行時間も短縮できたので良かったと思う(478[ms] ⇒ 3[ms]).
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 161 解説をご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/abc161/editorial.pdf #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--) int main(){ // 1. 入力情報. int K; scanf("%d", &K); // 2. 解説通り. LL ans; queue<LL> q; rep(i, 9) q.push(i + 1); while(1){ // Queue から 要素 を 取り出す. LL x = q.front(); q.pop(); // 操作を行う. LL r = x % 10; // 1の位を取得. for(LL d : {-1, 0, 1}){ LL a = r + d; // 1の位に, -1, 0, 1 を 加算. if(a >= 0 && a <= 9) q.push(10 * x + a); } // K回目であるかチェック. if(!(--K)){ ans = x; break; } } // 3. 出力. 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 |
[入力例] 15 [出力例] 23 ※AtCoderテストケースより [入力例] 1 [出力例] 1 ※AtCoderテストケースより [入力例] 13 [出力例] 21 ※AtCoderテストケースより [入力例] 100000 [出力例] 3234566667 ※AtCoderテストケースより [入力例] 123 [出力例] 1123 [入力例] 1234 [出力例] 222343 [入力例] 12345 [出力例] 33432123 [入力例] 123456 [出力例] 4455544433 |
■参照サイト
AtCoder Beginner Contest 161