LoginSignup
1
0

More than 1 year has passed since last update.

@Narangelife

桁DPの自己理解

Last updated at Posted at 2022-03-17

前置き

私はようやく桁DPが理解できた人なので、間違ってたり解釈ミスしていたらすみません。
他のサイトを見てもなかなか理解できなかった経験を踏まえて記事を書いています。

桁DPって？

動的計画法(Dynamic Programming)の一種で、桁ごとに考えていくアルゴリズムです。
AtCoderなどで、入力される値が$10^{10000}$のようにかなり大きいときに使えます。

桁DPの考え方

基本形
dp[i][smaller]
-> $i$( $\geq 1$)桁目まで決定して、$i$桁目が最大値の同一桁より小さいか(bool:smaller)

※"決定"というか、上位からi桁目の"場合分け"が完了した状態
※最大値: 入力で与えられた、問題となる値の範囲の最大値

例

最大値 $D = 71245_{(10)}$ の時:

dp[2][true]: 70999 ~ 00000 の暫定の答え
smaller:trueのためi=2桁目は、$D$の2桁目である1よりも1つ小さい0が最大となる。
すでに2桁目が$D$より小さいことが確定したため3桁目以降は0~9の値を各桁でとることができる。
-> 71*** 未満の数

dp[2][false]: 71199 ~ 71000 の暫定の答え
smaller:falseのためi=2桁目は、$D$の2桁目と同じ1となる。
2桁目は決定したが、3桁目は$D$の3桁目を超えないように注意。
-> 71*** となる数

※"暫定の答え"は、「～通り」みたいな。

image.png
※水色の括弧は範囲内をすべて持っているのではなく、"対象"としている。

dp[2][true]において2桁目が水色なのは、trueであるため最大値の2桁目未満であれば任意でよいためです。そのため「最大値の当桁未満であればいい」と決めた桁が2桁目までであるためdp[2]となっています。

遷移

DPなので漸化式として扱います。

dp[i][true] -> dp[i + 1][true]
$i$桁目の時点でsmaller:trueなら、$i + 1$桁目を自由に選んでも必ずsmaller:trueのまま。
(つまりsmaller:falseに遷移することはない)
※70*** なら 70?** もtrue

dp[i][false] -> dp[i + 1][true]
$i + 1$桁目に最大値の$i + 1$桁目より小さい数を選択した場合にはsmaller:trueに遷移。
※71*** -> 71?** (? < 2) はtrue

dp[i][false] -> dp[i + 1][false]
$i + 1$桁目に最大値の$i + 1$桁目と同じ数を選択した場合にはsmaller:falseに遷移。
※71*** -> 712** はfalse

※ここで示している例はすべて前述の例の$D = 71245$のものです。

上位桁から、なぜ考えられるのかは例題で説明しています。

例題: Educational DP Contest S問題

問題文

$1$ 以上 $K$ 以下の整数のうち、十進表記における各桁の数字の総和が $D$ の倍数であるようなものは何個か？
$10^9 + 7$ で割った余りを求めてください。

制約

  • 入力は整数
  • $1 \leq K \leq 10^{10000}$
  • $1 \leq D \leq 100$

桁DPを考えていく

この問題では、「各桁の和」を必要としており、和を考える際に各桁がどのような数字で組みあがっているかは重要ではありません。
そこで、$i + 1$桁目を考える際に動的計画法として渡す情報は「これまでに決定した桁分の和($\mod D$ )」とします。
そしてこの情報を元に、同じ和($\mod D$ )のものは同じ種類としてまとめられる(分類できる)ため、

考える桁DP
dp[i][smaller][j]
-> $j$ : 決定した桁の [和$\mod D$]

とします。

なぜ上位桁から考えて答えが出るのか？

そもそも、与えられた条件を検査する際に「検査対象がどのような数字から成り立っているのか」は重要ではありません。
条件を分類するものが分かればこれを次の桁決定に伝えていけば良いです。
そこで、この問題で$K = 71245$を例とすれば、例えば

  • 624** ($\Sigma = 6 + 2 + 4 = 12$)
  • 381** ($\Sigma = 3 + 8 + 1 = 12$)

は同じ分類(桁の和)として扱えます。※$\mod D$はここでは無視していますが実際は適用します。
つまり、「$i (= 3)$ 桁目決定の時点で和が12になるのが $x$ 通り」ということが分かっていれば、次($i + 1$桁目)にくる数字に応じて一気にその通り数を計算できます。
先ほどの例から続きを例に出すと、

  • 4桁目を1とすると、$i (= 4)$桁目決定時点で和が$(13 =12 + 1)$となるのは$x$通り
  • 4桁目を2とすると、$i (= 4)$桁目決定時点で和が$(14 =12 + 2)$となるのは$x$通り
  • ...

と漸化式のように通りが分かっていきます。(実際には$\mod D$があるので全部$x$通りになることはあまりないはず)
→ += で同一分類に加算してまとめればよい

いざ実装

"遷移"の章で書いたものを今回の[j]を適用できる形に変換します。

dp[i][true] -> dp[i + 1][true]
についてすでにsmaller:trueなのでi + 1桁目にありうるのは{0,1,2,...,9}です。
よって
dp[i + 1][true][(j + k) % D] += dp[i][true][j] (k = {0,1,2,...,9})
※日本語訳: i+1桁目にkを決定するとi+1桁目までの和はj + kとなる(jはi桁目までの和)

dp[i][false] -> dp[i + 1][true]
についてi + 1桁目には最大値の桁$K_{i+1}$より小さい数を指定します。
よって
dp[i + 1][true][(j + k) % D] += dp[i][false][j] (k = {0,1,2,...,$K_{i+1}$ - 1})

dp[i][false] -> dp[i + 1][false]
についてi + 1桁目には最大値の桁$K_{i+1}$と同じ数を指定します。
よって
dp[i + 1][false][(j + K) % D] += dp[i][false][j] (K = $K_{i+1}$)

初期値

漸化式には初項が必要です。

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

$i=0$ 桁目まで決定、とはどういうことでしょうか？
71245って、000000000...00071245とも書くことができます。
image.png

つまり、0桁目までsmaller:falseで決定しているとき、0桁目までは0000...00ということになります。
そしてこの桁和の$\mod D$ は必ず0となり1通りしかないことは明白です。
よって、0桁目まで決定し最大値の0桁目までが同一であまりが0のものは1通りとなり、dp[0][0][0]=1となります。

コーディング

↓参考

まず今回の基本的なテンプレートは

#include <iostream>
#include <string>

using namespace std;

int main(){

    return 0;
}

です。
$10^9 + 7$ で割った余りを求めたり、DPの配列が必要だったりするので

#include <iostream>
#include <string>
+ #define mod 1000000007
using namespace std;

//[i]は0~10000の計10001個。[smaller]は0,1の2個。[j]はDで割った余りなので0~99。(どれも制約の最大値を利用)
+ long long dp[10001][2][100];

int main(){

    return 0;
}

を用意し、そして入力を受け取って初期化します。

#include <iostream>
#include <string>
#define mod 1000000007
using namespace std;

long long dp[10001][2][100];

int main(){
+   string K;
+   int D;
+   cin >> K;
+   cin >> D;
+   dp[0][0][0] = 1;
    return 0;
}

int main()の外で配列を静的に宣言しておくことで初期値が0と自動的に設定されるので初期化が不必要。
そして桁送りのforと、各あまりごとの分類のforを回します。

#include <iostream>
#include <string>
#define mod 1000000007
using namespace std;

long long dp[10001][2][100];

int main(){
    string K;
    int D;
    cin >> K;
    cin >> D;
    dp[0][0][0] = 1;
+   for (int i = 0; i < K.size(); i++){
+       for (int j = 0; j < D; j++){
+           
+       }
+   }
    return 0;
}

$i + 1$ 桁目の値を遷移条件ごとに決定してforで回します。また、$i + 1$ 桁目の最大値を取得しておきます。

#include <iostream>
#include <string>
#define mod 1000000007
using namespace std;

long long dp[10001][2][100];

int main(){
    string K;
    int D;
    cin >> K;
    cin >> D;
    dp[0][0][0] = 1;
    for (int i = 0; i < K.size(); i++){
+       int ni = (K[i] - '0'); // i+1桁目の最大値の桁値
        for (int j = 0; j < D; j++){
+           for (int k = 0; k < ni; k++){
+               //dp[i][false] -> dp[i+1][true] 遷移
+               dp[i + 1][1][(j + k) % D] += dp[i][0][j];
+               dp[i + 1][1][(j + k) % D] %= mod;
+           }
+           for (int k = 0; k < 10; k++){
+               //dp[i][true] -> dp[i+1][true] 遷移
+               dp[i + 1][1][(j + k) % D] += dp[i][1][j];
+               dp[i + 1][1][(j + k) % D] %= mod;
+           }
+               //dp[i][false] -> dp[i+1][false] 遷移
+           dp[i + 1][0][(j + ni) % D] = dp[i][0][j] % mod;
        }
    }
    return 0;
}

基本的には足し算、掛け算のたびに%= modで値を小さくしておくと安心です。

そして最後に出力を書きます。
この時 $D$ の倍数かどうかは**あまり即ちjが0で確認できるので、

  • $K$ が $D$ の倍数か：dp[K.size()][0][0]
  • $K$ 未満での $D$ の倍数の個数：dp[K.size()][1][0]

しかし、"$K$ 未満"では0000...000が含まれているため、1通り引いておく必要があります。
よって

#include <iostream>
#include <string>
#define mod 1000000007
using namespace std;

long long dp[10001][2][100];

int main(){
    string K;
    int D;
    cin >> K;
    cin >> D;
    dp[0][0][0] = 1;
    for (int i = 0; i < K.size(); i++){
        int ni = (K[i] - '0'); // i+1桁目の最大値の桁値
        for (int j = 0; j < D; j++){
            for (int k = 0; k < ni; k++){
                //dp[i][false] -> dp[i+1][true] 遷移
                dp[i + 1][1][(j + k) % D] += dp[i][0][j];
                dp[i + 1][1][(j + k) % D] %= mod;
            }
            for (int k = 0; k < 10; k++){
                //dp[i][true] -> dp[i+1][true] 遷移
                dp[i + 1][1][(j + k) % D] += dp[i][1][j];
                dp[i + 1][1][(j + k) % D] %= mod;
            }
                //dp[i][false] -> dp[i+1][false] 遷移
            dp[i + 1][0][(j + ni) % D] = dp[i][0][j] % mod;
        }
    }
+   cout << dp[K.size()][0][0] + dp[K.size()][1][0] - 1 << endl;
    return 0;
}

となり、ACです！

お疲れ様でした！

1
0
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0