D – Lunlun Number 解説 (AtCoder Beginner Contest 161)

2020年4月4日AtCoder深さ優先探索,キュー,全探索,400点

問題へのリンク

問題概要

桁ごとに見た時、隣り合う数字の差の絶対値が 1 以下になる数を考える。小さいほうから K 番目の数を求めよ

制約

  • \(1 \leq K \leq 10^5\)

考え方

制約が結構重要です。小さい方から1つずつ全探索することができれば、求められそうだということが分かります。

特殊な条件を持つ数を小さい方から全探索する時（パナソニックプログラミングコンテスト2020 D – String Equivalence など）は、深さ優先探索（DFS）を使うことは良くあり、今回もDFSで全探索することが可能です。

ただ、DFSでやると実装が面倒なので、思いつくなら公式解説にある通り Queue を利用するほうが簡単です。

解法1: DFS

DFS で小さい方の数から全探索します。

桁を固定して、小さい桁から探索するのがやりやすいと思います。

C++ での実装例

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

int K;
int dfs(int k, int n, string s) {  // k: 何番目の数か, n: 何桁の数を探索するか
    if ((int)s.size() == n) {
        if (k == K) {
            cout << s << endl;
        }
        k++;
        return k;
    }
    if ((int)s.size() == 0) {
        for (int i = 1; i < 10; i++) {
            string ns = s;
            ns.push_back((char)(i + '0'));
            k = dfs(k, n, ns);
        }
    } else {
        for (int i = 0; i < 10; i++) {
            if (abs((int)(s.back() - '0') - i) <= 1) {
                string ns = s;
                ns.push_back((char)(i + '0'));
                k = dfs(k, n, ns);
            }
        }
    }
    return k;
}

int main() {
    cin >> K;
    int k = 1;
    int n = 1;
    while (k <= K) {
        k = dfs(k, n, "");
        n++;
    }
}

解法2: Queue

Queue を上手く利用すると簡単に全探索ができます。

先頭から取り出した値を一桁増やして最後尾に追加してやると、条件を満たす数が、順番に並びます。

取り出した数を n とすると、以下のように加えれば良いです。

  • n の 1 の位の数が 0 でないとき：n * 10 + (n % 10) – 1
  • すべての場合について：n * 10 + (n % 10)
  • n の 1 の位の数が 9 でないとき：n * 10 + (n % 10) + 1

これは幅優先探索(BFS)ということもできるでしょう。

C++ での実装例

サンプルに最大の時のケースがあるので、これを確認すると 64 bit 整数で収まることが分かります。実は string 型で保持する必要はないです。

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

int K;

int main() {
    cin >> K;
    queue<long long> que;
    for (int i = 1; i < 10; i++) {
        que.push(i);
    }
    for (int i = 0; i < K - 1; i++) {
        long long n = que.front();
        que.pop();
        if (n % 10 != 0) { que.push(n * 10 + (n % 10) - 1); }
        que.push(n * 10 + (n % 10));
        if (n % 10 != 9) { que.push(n * 10 + (n % 10) + 1); }
    }
    cout << que.front() << endl;
}

AtCoder深さ優先探索,キュー,全探索,400点