AtCoder: ABC161-D Lunlun Number (400)

問題はこちら

atcoder.jp

以下の条件を満たす正の整数 $X$ のうち、小さい方から $K$ 番目のものを求めよ。

$X$ を10進数で表した時、隣り合うどの二つの桁の値についても、差の絶対値が1以下。

考え方

基本的に解説放送を聞いて自分の言葉に直しただけ。

www.youtube.com

まずは桁ごとに考えてみる。すると、今までに列挙した数の後ろに、条件を満たすような数を付け加えていけば良いということに気づく。

1 -> 10, 11, 12
10 -> 100, 101
11 -> 110, 111, 112
12 -> 121, 122, 123

今まで条件を満たしていた数 $x$ の一の位 $x_1$ は $x \% 10$ 。
よって、次に条件を満たす数は $x$ を10倍した数に、次に条件を満たす $x_1, x_1 + 1, x_1 - 1$ をつけたものになる。

これを全列挙しても $K$ 個程度までに答えが得られるので、間に合う。

解答

$K$ 個全列挙するため、桁ごとに列挙したものの数を減らしていき、 $K$ が列挙してある数よりも小さくなった時、値を出力する。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ll k;
    cin >> k;
    vector<ll> a;
    for (ll i = 1; i <= 9; ++i) a.emplace_back(i);

    while (k > a.size()) {
        k -= a.size();
        vector<ll> old = a;
        a = vector<ll>();
        for (ll x: old) {
            for (ll i = -1; i <= 1; ++i) {
                ll d = x % 10 + i;
                if (d < 0 || 9 < d) continue;
                ll nx = x * 10 + d;
                a.emplace_back(nx);
            }
        }
    }
    cout << a[k - 1] << '\n';
    return 0;
}

Submission #11557806 - AtCoder Beginner Contest 161

ひらめの日常

日常のメモをつらつらと

AtCoder: ABC161-D Lunlun Number (400)

問題はこちら

考え方

解答