Digit Products [AtCoder Beginner Contest 208 E]

https://atcoder.jp/contests/abc208/tasks/abc208_e

前提知識

• 桁DP

解説

https://atcoder.jp/contests/abc208/submissions/23995133

桁DPの知識が必要になる。
桁DPに慣れていれば真っ先に桁DPが思い浮かびそうな問題設定であるので、
もし知らない場合は桁DPについて学習してきてほしい。
より簡単な問題もある。
この先知っている前提で話を進める。

桁DPのDPテーブル

以下のようなDPテーブルで計算を行う。

dp[digit][isLess][leadingZero][seki] :=
上からdigit桁目まで確定していて
既にNよりも小さいかどうかがisLess(=1なら既に小さい)であり、
まだ先頭の0であるかがleadingZeroであり、
各桁の数字の積がsekiである数の個数

digit, isLess, leadingZeroは桁DPでは普通に使うものなので特に説明しない。
（流派によって使ったり使わなかったりするかも）
ここでこの問題固有なのがsekiの部分である。

seki

アレなネーミングはさておき、ここに積を置いたら状態数がKになってダメでは？という疑問がある。
しかし、問題の性質上、ここはそれほど組み合わせ数が無く、状態に積を置くことができる。
各桁は0～9になるので、素因数的に考えると、2,3,5,7しか使われない。
例えば全部2であると仮定しても60個くらいしか含むことができない。
なので、雑に計算して、全部60個としても60⁴通りくらいだが、どう考えてもそれよりかはむっちゃ減る。
他の状態数も大したことないので、これは普通に間に合いそうと判断できる。
実際はちゃんと積の個数を計算した方がいい。

DP計算

まず、DP定義についてだが、こういった、数は大きくなりうるが使用される状態数がそれほど多くない
という場合はmap（dictionary型）で定義して使用するのがいい。
後は桁DPに従って頑張って書いていくしかない。

一応自分の実装について方針を軽く書いておく。
dp[digit][isLess][leadingZero][seki]から、nxtという数をdigit桁に置く場合を考える。
～2は次の状態。

• digit2はdigit+1（1桁確定するので）
• isLess2はnxtが現在の数より小さかったら1(=true)になる、そうでないならisLessのまま
• leadingZero2はnxtが0以外なら0(=false)になる、そうでないならleadingZeroのまま
• sekiはnxtをかける（leadingZeroが1ならまだ数が始まってないのでかけない）

注意点として最初の状態はdp[0][0][1][1]=1であるということと、sekiは基本K以下で打ち切ればいいのだが、
Kより大きくなっても0が出てきたら総積が0になるので問題ない。
よって、Kより大きくなった場合でも切り捨てるのではなくinfとしてKより大きいというひとくくりの状態として
保持していく。
あとは、桁あふれとかに注意。
桁DPはとにかくバグるので頑張ってほしい。

string N; int K;
map<int, ll> dp[20][2][2];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    int M = N.size();

    dp[0][0][1][1] = 1;
    rep(digit, 0, M) rep(isLess, 0, 2) rep(leadingZero, 0, 2) fore(p, dp[digit][isLess][leadingZero]) {
        int seki = p.first;
        ll com = p.second;

        int cur = N[digit] - '0';

        rep(nxt, 0, 10) {
            if (isLess == 0 && cur < nxt) continue;

            int digit2 = digit + 1;

            int isLess2 = isLess;
            if (nxt < cur) isLess2 = 1;

            int leadingZero2 = leadingZero;
            if (0 < nxt) leadingZero2 = 0;

            int seki2 = seki;
            if (leadingZero2 == 0) {
                if (K < 1LL * seki * nxt) seki2 = inf;
                else seki2 *= nxt;
            }

            dp[digit2][isLess2][leadingZero2][seki2] += com;
        }
    }

    ll ans = 0;
    rep(isLess, 0, 2) fore(p, dp[M][isLess][0]) if (p.first <= K) ans += p.second;
    cout << ans << endl;
}