短歌数 [ACM-ICPC JAG 模擬国内予選 2018年 D]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Prelim/2884

考察過程

1. パット見て、二分探索するアレとか桁DPとかという雰囲気を察する
2. サンプルの答えを見るとあまりにでかすぎる答えがあるので、二分探索だと多倍長整数を使う必要があるので違うかも
3. 小さい数から順に数えていって、辞書順に答えを導く方針で考える（高校数学のこれと全く同じ考え方）
4. 先頭の数と桁数を全探索していく
5. 先頭の数と桁数が決まったら、上の桁から辞書順でまた数えていって確定していけばいい
6. これなら間に合いそう

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/2884/review/3000669/hamayanhamayan/C++14

辞書順に個数を数えていって、先頭から数を確定させていく方針で解く。
N--をして0-indexedにしておくと、N-cn＜0ならばそのグループの中にいることが分かる。
　
複数関数を用意して段階的に確定させていく
solve() := 答えが出てくる（先頭の数と桁数を全探索して探す）
f(n, a) := 使う数がaだけ確定していて答えの下位n桁分の数を返す（どれだけ先頭から1種類の数を使うかと2種類目の数の特定をする）
g(n, a, b) := 使う数がa,b（a＜b）で答えの下位n桁分の数を返す
　
solve関数
先頭の数がaでn桁の短歌数の場合の数は(2^(n-1) - 1) * 9通りある。
これで、(a,n)の組を探そう
　
f(n,a)関数
n桁目がaとなるn桁の短歌数の場合の数は(2^(n-1) - 1) * 9通りある。
このグループに属する場合はn桁目をaとしてf(n-1,a)に処理を任す。
n桁目がb(a≠b)となるn桁の短歌数の場合の数は2^(n-1)通りある。
このグループに属する場合はn桁目をbとしてg(n-1,a,b)に処理を任す。
　
g(n,a,b)関数
n桁目がaとなる場合でも、bとなる場合でも、n桁の短歌数の場合の数は2^(n-1)通りある。
個数を見ながらaが入るかbが入るか確定させてg(n-1,a,b)に処理を移していく。

ll N, bit[101];
//---------------------------------------------------------------------------------------------------
string g(int n, int a, int b) {
    if (n == 0) {
        if (N == 0) return "";
        else return "?";
    }

    ll cn = bit[n - 1];
    if (N - cn < 0) {
        string res = "";
        res += char('0' + a);
        return res + g(n - 1, a, b);
    }

    N -= cn;
    string res = "";
    res += char('0' + b);
    return res + g(n - 1, a, b);
}
//---------------------------------------------------------------------------------------------------
string f(int n, int a) {
    rep(b, 0, 10) {
        ll cn;
        if (a == b) cn = (bit[n - 1] - 1) * 9;
        else cn = bit[n - 1];

        if (N - cn < 0) {
            string res = "";
            res += char('0' + b);

            if (a == b) res += f(n - 1, a);
            else res += g(n - 1, min(a, b), max(a, b));
            return res;
        } else N -= cn;
    }
}
//---------------------------------------------------------------------------------------------------
string solve() {
    N--;

    rep(n, 2, 100) rep(a, 1, 10) {
        ll cnt = (bit[n - 1] - 1) * 9;
        if (N - cnt < 0) {
            string ans = "";
            ans += char('0' + a);
            return ans + f(n - 1, a);
        }
        N -= cnt;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    bit[0] = 1;
    rep(i, 1, 101) bit[i] = bit[i - 1] * 2;

    while (cin >> N) {
        if (N == 0) return;
        auto ans = solve();
        printf("%s\n", ans.c_str());
    }
}