[AtCoder] ABC 161 D – Lunlun Number

2020年4月5日2020年12月15日

問題

方針

数字の桁数を増やすことで新たなルンルン数を得ることを考えます。あるルンルン数 \( s \) の末尾の数字を \( d \) とすると、\( 10s + d, 10s + d – 1 , 10s + d + 1 \) がルンルン数の候補になります。\( d = 9 \) のときは、\( 10s + d + 1 \) がルンルン数でない可能性があり、\( d = 0 \) のときは、\( 10s + d – 1 \) がルンルン数でない可能性に注意します。制約内ではルンルン数は高々 \( 10 \) 桁なので、\( i \) 桁のルンルン数全てに対して、\( i + 1 \) 桁のルンルン数を求めます。求めた後は、整列させて解答を得ます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool my_compare(string a, string b) {
    if (a.length() == b.length()) {
        for (int i = 0; i < a.length(); i++) {
            if (a[i] != b[i]) {
                return a[i] < b[i];
            }
        }
        return true;
    } else {
        return a.length() < b.length();
    }
}

int main() {
    int K;
    cin >> K;
    set<string> s;
    set<string> tmp1{"1", "2", "3", "4", "5", "6", "7", "8", "9"};
    for (int i = 1; i <= 9; i++) {
        s.insert(to_string(i));
    }
    for (int i = 0; i < 9; i++) {
        set<string> tmp2;
        for (string t : tmp1) {
            tmp2.insert(t + t.back());
            s.insert(t + t.back());
            if (t.back() == '9') {
                s.insert(t + '8');
                tmp2.insert(t + '8');
            } else if (t.back() == '0') {
                s.insert(t + '1');
                tmp2.insert(t + '1');
            } else {
                char c1 = (char)(t.back() - 1);
                char c2 = (char)(t.back() + 1);
                s.insert(t + c1);
                s.insert(t + c2);
                tmp2.insert(t + c1);
                tmp2.insert(t + c2);
            }
        }
        tmp1 = tmp2;
    }
    vector<string> list;
    for (string t : s) {
        list.push_back(t);
    }
    sort(list.begin(), list.end(), my_compare);
    cout << list[K - 1] << "\n"; 
    return 0;
}