問題概要

各桁の数値が狭義単調減少になっている数を 321-like 数と呼ぶ。

$K$ 番目の 321-like 数を求めよ。

制約

$K \le$ 321-like 数の個数

解法 (1)：異常 10 重 for 文

この解法は本当に根性で解くタイプの方法になる。

考えられる最大の 321-like 数は、9876543210 となる。そして 321-like 数とは、これらの数値を歯抜けにすることで得られる。よって、

9 を使うか使わないか
8 を使うか使わないか
7 を使うか使わないか
...
0 を使うか使わないか

をそれぞれ分岐する 10 重の for 文でこの問題は解ける。なお、321-like 数の個数を見積もっておこう。9, 8, 7, ..., 0 という 10 個の数それぞれについて、「使う」か「使わない」かの 2 択ずつがあるため、321-like 数は多くても

$2^{10} = 1024$ 個

と見積もることができる。正確には、

すべて使わない　→　0 に対応
0 のみを使う　→　これも 0 に対応

という 2 ケースを除外する必要があるため、 $1024 - 2 = 1022$ 個である。

コード

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

int main() {
    // 321-like 数をすべて列挙する
    vector<long long> vals;
    
    // 各数 9, 8, ..., 0 について、使うなら 1、使わないなら 0
    vector<int> a(10);
    for (a[9] = 0; a[9] < 2; ++a[9]) {
        for (a[8] = 0; a[8] < 2; ++a[8]) {
            for (a[7] = 0; a[7] < 2; ++a[7]) {
                for (a[6] = 0; a[6] < 2; ++a[6]) {
                    for (a[5] = 0; a[5] < 2; ++a[5]) {
                        for (a[4] = 0; a[4] < 2; ++a[4]) {
                            for (a[3] = 0; a[3] < 2; ++a[3]) {
                                for (a[2] = 0; a[2] < 2; ++a[2]) {
                                    for (a[1] = 0; a[1] < 2; ++a[1]) {
                                        for (a[0] = 0; a[0] < 2; ++a[0]) {
                                            // 1 が立っている箇所のみで数値を作る
                                            long long val = 0;
                                            for (int i = 9; i >= 0; --i) {
                                                if (a[i] == 1) {
                                                    val = val * 10 + i;
                                                }
                                            }
                                            if (val > 0) vals.push_back(val);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    // 321-like 数を小さい順に並び替える
    sort(vals.begin(), vals.end());
    
    // K 番目を答える
    long long K;
    cin >> K;
    cout << vals[K-1] << endl;
}

解法 (2)：再帰関数

上のような幾重もの for 文は、再帰関数で綺麗に記述できる。詳しいことは次の記事に書いた。

drken1215.hatenablog.com

今回のもバッチリはまる。ちょうど、問題例としてあげている「AtCoder ABC 114 C - 755」や「AtCoder ABC 161 D - Lunlun Number」と同じような再帰関数で解ける。

コード

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

// 321-like 数をすべて列挙する再帰関数
// val: 途中経過の数
// vals: 321-like 数をすべて格納した配列
void rec(long long val, vector<long long> &vals) {
    // vals に val を加えておく
    vals.push_back(val);
    
    // 終端条件：val の一の位が 0 ならば終了 (実は
    if (val % 10 == 0) return;
    
    // val の末尾に「val の一の位の値」未満の数を追加するのを順に試す
    for (int i = 0; i < (val % 10); ++i) {
        long long val2 = val * 10 + i;
        rec(val2, vals);
    }
}

int main() {
    // 321-like 数をすべて列挙する (先頭の要素は 9, 8, ..., 1)
    vector<long long> vals;
    for (int v = 9; v >= 1; --v) rec(v, vals);
    
    // 321-like 数を小さい順に並び替える
    sort(vals.begin(), vals.end());
    
    // K 番目を答える
    long long K;
    cin >> K;
    cout << vals[K-1] << endl;
}

解法 (3)：ビット全探索

最後に、今回は 9, 8, 7, ..., 0 に対して、それぞれ「使う」か「使わない」かの 2 択ずつがあったことを思い出すと、ビット全探索でも解けることがわかる。

コード

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

int main() {
    // 321-like 数をすべて列挙するビット全探索
    vector<long long> vals;
    for (int bit = 0; bit < (1<<10); ++bit) {
        long long val = 0;
        
        // 9, 8, 7, ..., 0 をそれぞれ使うかを試す
        for (int v = 9; v >= 0; --v) {
            // 使う場合
            if (bit & (1 << v)) {
                val = val * 10 + v;
            }
        }
        if (val > 0) vals.push_back(val);
    }
    
    // 321-like 数を小さい順に並び替える
    sort(vals.begin(), vals.end());
    
    // K 番目を答える
    long long K;
    cin >> K;
    cout << vals[K-1] << endl;
}