桁DP(Digit DP) を考え方から問題例まで徹底解説！

2020年2月14日2020年9月2日動的計画法DP,桁DP,テーマ記事,競プロ

競技プログラミングで良く用いられる動的計画法の1つ「桁DP」について解説します。

桁DPとは

桁ごとに分けて考える動的計画法です。

• 「1からNまでの整数について、条件を満たす数はいくつあるか？」
• 「1からNまでの整数について、条件を満たす最大値は何か？」

というような問題で主に使えます。

Nについての制約が非常に大きくなるのが特徴で、O(logN)やO(1)でないと計算時間が間に合わない問題で使用されます。

桁DPの前に知っておくと良いこと

桁DPでは、「N以下の数を全て走査する」ことになりますが、以下のような場合分けを考慮しておくと分かりやすくなります。

例えば、N=63435 のような数であれば、

• 00000 ~ 59999 (\(6\cdot 10^4\) 通り)
• 60000 ~ 62999 (\(3\cdot 10^3\) 通り)
• 63000 ~ 63399 (\(4\cdot 10^2\) 通り)
• 63400 ~ 63429 (\(3\cdot 10^1\) 通り)
• 63430 ~ 63434 (\(5\cdot 10^0\) 通り)
• 63435 (\(1\) 通り)

のような場合分けをすることを考えておきましょう。

このような場合分けを頭に入れておくと、桁DPが非常に理解しやすくなります。

桁DPの基本的な考え方

基本は以下のようなDPを考えます。

例えば、N=63435 について、

• dp[3][true] : 634○○未満となる数(00000 ~ 63399 )についての暫定の答え
• dp[3][false] : 634○○ となる数(63400 ~ 63429)についての暫定の答え

などを考えることになります。

桁DPの遷移

動的計画法なので、前に計算した内容を後で利用しましょう。

dp[ i ][smaller] からdp[ i+1 ][smaller] への遷移を考えるときは以下のようにsmaller のブール値によって分けて考えることができます。

• dp[ i ][true] からはdp[ i+1 ][ture]にのみ遷移( i桁目まででNより小さいなら i+1桁目をどのように選んでもNより小さい）
• dp[ i ][false] からdp[ i+1 ][ture]へ遷移( i桁目までNと同じで、 i+1桁目はNより小さい数の時)
• dp[ i ][false] からdp[ i+1 ][false]へ遷移( i桁目までNと同じで、 i+1桁目もNと同じ数の時)

i 桁目まで N よりも小さいものは、i+1桁目をどのように選んでもNと同じになることはありえません。
よって、dp[ i ][true] からはdp[ i+1 ][false]への遷移は起きません。

例題1：Typical DP Contest E – 数

例題として、Typical DP Contest E – 数 を考えながら、桁DPへの理解を深めて行きましょう。

問題概要

N 以下の正整数であって、十進法表記したときの各桁の数の和が D の倍数であるものの個数を mod 1,000,000,007 で求めよ。

• \(1 \leq N \leq 10^{10000}\)
• \(1 \leq D \leq 100\)

まず桁DPで解けると見抜く

桁DPで解ける問題は、

• Nが非常に大きく64bitで収まらない
• 「N以下の整数」について条件に合うものを数える

ような問題です。

今回の問題は2つの条件を満たしているので、桁DPが使えそうです。

DPを考える

基本は先程の

dp[ i ][smaller] := i 桁目まで決めた時の暫定の答え

を用いることになります。

しかし、i+1桁目までを決めた時に「各桁の数の和が D の倍数か」を得るためには、i桁目までを決めた時に「各桁の数の和が mod D でいくつか」が分かっていないと計算することができません。

例えば、N=63435, i=2 の時の1例である、63○○○について考えます。3桁目まで決めると、

• 630○○ 各桁の数の和は、9+0 で9
• 631○○ 各桁の数の和は、9+1 で10
• 632○○ 各桁の数の和は、9+2 で11
• 633○○ 各桁の数の和は、9+3 で12
• 634○○ 各桁の数の和は、9+4 で13

だけ可能性があります。「i+1桁目まで決めた時の暫定の答え」を出すためには、「i桁目までの各桁の数の和が 9」という情報が不可欠です。

つまり、以下のようなDPを考えればうまくいきます。

DPの遷移方法

基本は以下の全ての場合を考えればOKです。

• dp[ i ][true] からはdp[ i+1 ][ture]にのみ遷移
• dp[ i ][false] からdp[ i+1 ][ture]へ遷移
• dp[ i ][false] からdp[ i+1 ][false]へ遷移

今回は dp[ i ][smaller][ j ] について考えるので、これを少し変形して、

• dp[i + 1][true][(j + k) % D] += dp[ i ][true][ j ] (k = 0,1,2,…,9)
• dp[i + 1][true][(j + k) % D] += dp[ i ][false][ j ] (k = 0,1,2,…,\(N_i\))
• dp[i + 1][false][(j + \(N_i\)) % D] = dp[ i ][false][ j ]

というように更新してあげれば良いです。(\(N_i\)はNのi桁目の数)

最終的な答え

最終的には

• Nが D の倍数か：dp[n][0][0]
• N以下の数がいくつ D の倍数か：dp[n][1][0]

を用いて、 dp[n][0][0]+ dp[n][1][0] – 1　が答えになります。

この式に含まれる「-1」 は、dp[n][1][0]に、0 の時が余分に加えられているのでそれを取り除いています。

実装例

答えは mod 1,000,000,007 で求める必要があるのを忘れないようにしましょう。

#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = n; i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int MOD = 1e9 + 7;

int D;
string N;
ll dp[10005][2][105];

int main() {
    cin >> D >> N;
    int n = N.size();
    dp[0][0][0] = 1;
    REP(i, n) {
        REP(j, D) {
            // i桁目まででNより小さいならi+1桁目は何でも良い
            REP(k, 10) {
                dp[i + 1][1][(j + k) % D] += dp[i][1][j];
                dp[i + 1][1][(j + k) % D] %= MOD;
            }

            int ni = (N[i] - '0');

            // i桁目までNと同じで、i+1桁目はNより小さい数の時
            REP(k, ni) {
                dp[i + 1][1][(j + k) % D] += dp[i][0][j];
                dp[i + 1][1][(j + k) % D] %= MOD;
            }

            //  i桁目までNと同じで、i+1桁目もNと同じ数の時
            dp[i + 1][0][(j + ni) % D] = dp[i][0][j];
        }
    }

    cout << dp[n][0][0] + dp[n][1][0] - 1 << endl;

    return 0;
}

例題2：[AtCoder] ABC029 D – 1

問題へのリンク：[AtCoder] ABC029 D – 1

問題概要

N以下の全ての正整数について、1 は何回出現するか？

• \(1 \leq N \leq 10^{9}\)

考え方

この問題も桁DP的な考え方で解くことができます。

1 の出現回数を求めたいので、「1 が j 回出現する数がいくつあるか」を求めることを考えます。

とすると、

\( \sum_{j=1}^{9} j\cdot\) (dp[Nの桁数][true][ j ]+dp[Nの桁数][false][ j ])

によって答えが求まります。

実装例

詳しい場合分けなどはソースコード中のコメントなどを参考にしてください。

#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = n; i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int MOD = 1e9 + 7;

string N;
ll dp[11][2][11];

int main() {
    cin >> N;
    int n = N.size();

    dp[0][0][0] = 1;

    REP(i, n) {
        REP(j, 10) {
            // i桁目まででNより小さいならi+1桁目は何でも良い
            dp[i + 1][1][j] += dp[i][1][j] * 9;  // i+1桁目が1以外
            dp[i + 1][1][j + 1] += dp[i][1][j];  // i+1桁目が1

            int ni = (N[i] - '0');

            // i桁目までNと同じで、i+1桁目はNより小さい数の時
            if (ni > 1) {
                dp[i + 1][1][j] += dp[i][0][j] * (ni - 1);  // i+1桁目が0~ni-1のうちの1以外
                dp[i + 1][1][j + 1] += dp[i][0][j];         // i+1桁目が1
            } else if (ni == 1) {
                dp[i + 1][1][j] += dp[i][0][j];  // i+1桁目が0
            }

            //  i桁目までNと同じで、i+1桁目もNと同じ数の時
            if (ni == 1) {
                dp[i + 1][0][j + 1] = dp[i][0][j];  // i+1桁目が1
            } else {
                dp[i + 1][0][j] = dp[i][0][j];  // i+1桁目が1以外
            }
        }
    }

    ll ans = 0;
    REP(j, 10) { ans += (dp[n][0][j] + dp[n][1][j]) * j; }

    cout << ans << endl;

    return 0;
}

練習問題

• [AtCoder] ABC117 D – XXOR
• [AtCoder] ABC127 E – Sum Equals Xor：2進数での桁DPです
• [AtCoder] ABC007 D – 禁止された数字
• [AtCoder] Educational DP Contest S – Digit Sum

参考サイト

桁DPについて更に知りたい方はこちらの記事を見ると良いと思います。

• http://drken1215.hatenablog.com/entry/2019/02/04/013700
• https://torus711.hatenablog.com/entry/20150423/1429794075
• http://luzhiled.hatenablog.com/entry/2017/12/03/124453
• https://qiita.com/pinokions009/items/1e98252718eeeeb5c9ab