C++の練習を兼ねて, AtCoder Beginner Contest 161 の 問題D (D – Lunlun Number) を解いてみた.
■感想.
1. 個人的には, 非常に面白い問題に感じた.
※ 但し, かなり重たい実装になってしまったので, 解説を, 勉強しようと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト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 45 46 47 48 49 50 51 52 |
#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--) // Lunlun数のリストを更新する. // @param s: (更新前)Lunlun数情報のリスト. // @return ret: (更新後)Lunlun数情報のリスト. set<LL> updateLunlun(set<LL> s){ set<LL> ret; for(auto &o : s){ LL r = o % 10; // 1の位を取得. for(LL d : {-1, 0, 1}){ LL a = r + d; // 1の位に, -1, 0, 1 を 加算. if(a >= 0 && a <= 9) ret.insert(o), ret.insert(10 * o + a); } } return ret; } int main(){ // 1. 入力情報. int K; scanf("%d", &K); // 2. Lunlun数 を 保存. set<LL> s; rep(i, 9) s.insert(i + 1); rep(i, 10){ set<LL> ls = updateLunlun(s); swap(s, ls); } // 3. K番目 を 取得. LL ans = 0; int count = 0; for(auto &p : s){ if(++count == K){ ans = p; break; } } // 4. 出力. 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