<-- home

AtCoder ABC 161

April 18, 2020

https://atcoder.jp/contests/abc161

ABC161に参加したのでメモ。

A B C D E F
o o o o x x

A~Dは問題なく解けた。

D - Lunlun Number

桁DP + 二分探索で解いた。ある正の整数に対して、以下のルンルン数を数えることができれば、二分探索でK番目のルンルン数を見つけることができる。 桁DPでは、ある桁の数がleading zeroなのかどうかに注意して遷移を考える。

桁DPについては、似たような問題として、

がある。

こういう問題は桁DPを使えば脳死で解けるが、そうして解いても学びが得られない。あとで解説にあるようにBFSで解くなどしたい。

#define MAX_DIGIT 30

i64 dp[MAX_DIGIT + 1][2][2][10];
// [決定した桁数][未満フラグ][leading zeros][その桁の数字]


i64 count_lum(i64 n) {
    string ns = to_string(n);
    i64 L = ns.length();
    REP(i, L + 1) REP(j, 2) REP(k, 2) REP(d, 10) dp[i][j][k][d] = 0;
    dp[0][0][1][0] = 1;

    REP(i, L) {
        i64 D = ns[i] - '0';
        REP(smaller, 2) {
            REP(zeros, 2) {
                REP(d_prev, 10) {
                    for (i64 d = 0; d <= (smaller ? 9 : D); d++) {
                        if (zeros) {
                            dp[i + 1][smaller || d < D][d == 0][d]
                                 += dp[i][smaller][zeros][d_prev];
                        } else if (abs(d - d_prev) <= 1) {
                            dp[i + 1][smaller || d < D][0][d
                                 += dp[i][smaller][zeros][d_prev];
                        }
                    }
                }
            }
        }
    }

    i64 res = 0;
    REP(i, 10) res += dp[L][0][0][i] + dp[L][1][0][i];
    return res;
}


#define INF 1152921504606846976

int main() {
    i64 K; cin >> K;
    // x以下のるんるん数を数える

    i64 lb = 0, ub = INF;
    while (ub - lb > 1) {
        i64 mid = (lb + ub) / 2;
        if (count_lum(mid) >= K) {
            ub = mid;
        } else {
            lb = mid;
        }
    }

    cout << ub << endl;

    return 0;
}