<-- home

AtCoder ABC 114 C

April 2, 2020

https://atcoder.jp/contests/abc114/tasks/abc114_c

ABC 114 C問題を解説と異なり、桁DPで解いたのでメモ。

1. 桁DP

「N以下の非負整数で、~を満たすものを数える」という問題でよく使われる、DPの一種。

1.1 N以下の非負整数の総数を求める

以下の非負整数を求めるという問題について考える。この問題は桁DPを使わずとも、答えが個であることは明らかだが、あえて桁DPで解いてみる。

の桁数をとして、

と表す。例えば、なら, , となる。

この問題は、個のに0-9を、N以下という条件を満たすように当てはめる問題と同じ(はに対応するようにleading zerosを許すこととする)。

まず、の桁に対応するに0-9を当てはめたい。を当てはめれば、N以下という条件を満たすことができる。ここで、を当てはめた場合には、その時点で、それ以降に何を当てはめても、N以下であることが確定する。例えば、で、に0か1を当てはめたとき、0**, 1**となり、いずれも残りのに何を当てはめてもN以下である。

次に、の桁に対応するに0-9を当てはめたい。桁を決めたとき、すでにN以下であることが確定しているのであれば、0-9を当てはめることができる。そうでないならば、を当てはめることができる。先ほどと同様に、N以下であることが確定していない場合に、(つまりそれまでの桁にNと同じ数字を割り当てている場合に)、を割り当てたとすると、その時点で、それ以降に何を当てはめても、N以下であることが確定する。

以降の桁についてもこれを繰り返す。この一連の手順をDPで表したい。

状態は、で必要十分。遷移は、

実装

// テンプレ省略

#define MAX_DIGIT 100
i64 dp[MAX_DIGIT + 1][2];

int main() {
    string N; cin >> N;
    i64 L = N.length();

    REP(i, L + 1) REP(j, 2) {
        dp[i][j] = 0;
    }
    dp[0][0] = 1;

    REP(i, L + 1) {
        i64 D = N[i] - '0';
        REP(smaller, 2) {
            for (i64 d = 0; d < (smaller ? 10 : D + 1); d++) {
                dp[i + 1][smaller || (d < D)] += dp[i][smaller];
            }
        }
    }

    i64 ans = dp[L][0] + dp[L][1];
    cout << ans << endl;

    return 0;
}

C問題

1以上N以下の「753数」を数える問題。 753数は、「十進法で表記したとき、数字 7, 5, 3 がそれぞれ1回以上現れ、これら以外の数字は現れない」数と定義される。

上のN以下の非負整数を数える場合と基本的には同じ。状態をいくつか増やすだけ。桁DPで数える場合の注意点は、のように753数の先頭に0がくっついているものも数えなければいけないこと。これに注意して、状態を考えると、

となる。フラグは4ビットとして、上位3桁をそれぞれ7,5,3を使ったかどうか, 下位1桁をそれ以外の数字を使ったかどうかを表す。例えば、1010は7が一回以上、5が0回、3が1回以上、それ以外の数字が0回使われたことを表す。

実装

#define MAX_N 999'999'999
#define MAX_DIGIT 9
#define N_BIT 4
i64 dp[MAX_DIGIT + 1][2][2][1 << N_BIT];

int main() {
    string N; cin >> N;
    i64 L = N.length();

    REP(i, 2) REP(j, 2) REP(k, 1 << N_BIT) {
        dp[0][i][j][k] = 0;
    }
    dp[0][0][1][0] = 1;

    auto flag = [&](i64 d) {
        if      (d == 7) return (1 << 3);
        else if (d == 5) return (1 << 2);
        else if (d == 3) return (1 << 1);
        else             return (1 << 0);
    };

    REP(l, L) {
        i64 D = N[l] - '0';
        REP(smaller, 2) {
            REP(only_zero, 2) {
                REP(bit, 1 << N_BIT) {
                    for (i64 d = 0; d < (smaller ? 10 : D + 1); d++) {
                        if (only_zero && d == 0) {
                            dp[l + 1][smaller || d < D][1][bit] 
                                += dp[l][smaller][only_zero][bit];
                        } else {
                            dp[l + 1][smaller || d < D][0][bit | flag(d)]
                                += dp[l][smaller][only_zero][bit];
                        }
                    }
                }
            }
        }
    }

    cout << dp[L][0][0][14] + dp[L][1][0][14] << endl;

    return 0;
}