桁DP入門

(2018年12月27日)言葉足らずの箇所も多かったので全体的に書き換えました。昔のほうが良かったと思うのであれば、おそらく Internet Archive で見れるのでそちらで見るといいと思います。少し単純化した記事もかいたので暇な人は読んでみてください。 pekempey.hatenablog.com

$A$ 以下の非負整数のうち「3の倍数または3の付く」かつ「8の倍数でない」数がいくつあるか求めてみよう。でもいきなりこの問題を解くのは難しいと思うので、

  1. $A$ 以下の非負整数の総数を求める
  2. $A$ 以下の非負整数のうち、3の付く数の総数を求める
  3. $A$ 以下の非負整数のうち、「3が付くまたは3の倍数」の数の総数を求める
  4. $A$ 以下の非負整数のうち、「3が付くまたは3の倍数」かつ「8の倍数でない」数の総数を求める

という4つの問題を順に解くことにしよう。

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

左から順に数字を決めていこう。 左から 4175 と決めたあとの状況を考えてみる。 f:id:pekempey:20151208203458p:plain
? に入りうる数字は何だろう。これは 0 から 9 のどれでもいい。上から 2 桁目が $A$ より小さいので ? に何を選んでも $A$ 以上にはならないからだ。次の場合はどうだろう。
f:id:pekempey:20151208203812p:plain
この場合 ? に入りうるのは 0 から 6 だけである。この 2 つの違いは確定してる桁の中に $A$ より小さいものがあるかどうかだけだ。だから 4175 とか 4275 みたいな具体的な以前の桁を覚えていなくても、そういう桁があるかどうかだけ覚えていればよい。つまり 4175 のかわりに less=1 と書いて、4275 のかわりに less=0 と書いてあってもその先の処理に支障はでない。

f:id:pekempey:20151208204204p:plain
less=1なら ? に入るのは 0 から 9 の数字である。

f:id:pekempey:20151208204130p:plain
less=0なら ? に入るのは 0 から 6 の数字である。このことを踏まえてコードにしてみると次のようになる。添字の $i$, $j$ はそれぞれ「上位 $i$ 個の桁を決めた」「$A$ 未満が確定している」を表している。$x$ というのがいま使える最大の値で、$j=0$ なら $A[i]$ までしか使えないし、$j=1$ なら 9 まで使えるのはさっき話したとおり。j || d < x という部分がトリッキーに見えるけど、もともと $j=1$ だったら $A$ 未満が確定しているし、$d<x$ だったら $A$ 未満が確定するので、ということを言っている。

桁 DP の問題は与えられる N がものすごく大きくて、int とか long long では収まらないから文字列として受け取らないといけないことが多い。だからここでもそうする。オーバーフローは気にせず書いてるけど、基本的には mod をとらないとダメ。

#include <iostream>
#include <string>

using namespace std;

string A;
int dp[100001][2];

int main() {
    cin >> A;
    const int n = A.size();
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            int x = j ? 9 : A[i] - '0';
            for (int d = 0; d <= x; d++) {
                dp[i + 1][j || d < x] += dp[i][j];
            }
        }
    }
    int ans = 0;
    for (int j = 0; j < 2; j++) {
        ans += dp[n][j];
    }
    cout << ans << endl;
}

A以下の非負整数のうち、3の付く数の総数を求める

すでに 3 を使ったかどうかも覚えておけばよい。添字の $i$, $j$, $k$ はそれぞれ「上位 $i$ 個の桁を決めた」「$A$ 未満が確定している」「確定した桁のなかに 3 がある」である。

#include <iostream>
#include <string>

using namespace std;

string A;
int dp[100001][2][2];

int main() {
    cin >> A;
    const int n = A.size();
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                int x = j ? 9 : A[i] - '0';
                for (int d = 0; d <= x; d++) {
                    dp[i + 1][j || d < x][k || d == 3] += dp[i][j][k];
                }
            }
        }
    }
    int ans = 0;
    for (int j = 0; j < 2; j++) {
        ans += dp[n][j][1];
    }
    cout << ans << endl;
}

A以下の非負整数のうち、「3が付くまたは3の倍数」の数の総数を求める

mod 3の値も覚えておけばよい。添字の $i$, $j$, $k$, $l$ はそれぞれ「上位 $i$ 個の桁を決めた」「$A$ 未満が確定している」「確定した桁のなかに 3 がある」「確定部分を mod 3 した値」である。

「3 が付くまたは 3 の倍数」という条件は ans のところで考慮している。

#include <iostream>
#include <string>

using namespace std;

string A;
int dp[100001][2][2][3];

int main() {
    cin >> A;
    const int n = A.size();
    dp[0][0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                for (int l = 0; l < 3; l++) {
                    int x = j ? 9 : A[i] - '0';
                    for (int d = 0; d <= x; d++) {
                        dp[i + 1][j || d < x][k || d == 3][(l + d) % 3] += dp[i][j][k][l];
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
            for (int l = 0; l < 3; l++) {
                if (k || l == 0) {
                    ans += dp[n][j][k][l];
                }
            }
        }
    }
    cout << ans << endl;
}

A以下の非負整数のうち、「3が付くまたは3の倍数」かつ「8の倍数でない」数の総数を求める

添字の $i$, $j$, $k$, $l$, $ m $ はそれぞれ「上位 $i$ 個の桁を決めた」「$A$ 未満が確定している」「確定した桁のなかに 3 がある」「確定部分を mod 3 した値」「確定部分を mod 8 した値」である。

mod 8 の値の求め方がすこし奇妙かもしれない。すでに決まってる部分を $X$ として新しく決めた桁を $D$ とすると $10X+D$ ができあがる。$X \bmod 8$ の値が $ m $ だったら $(10X+D) \bmod 8$ は $(10m+D) \bmod 8$ だから、という考えで求めている。

このくらいになるとネストがすごいことになる。むかしの自分は REP に切り替えてたけど、慣れればこれでも平気。

#include <iostream>
#include <string>

using namespace std;

string A;
int dp[100001][2][2][3][8];

int main() {
    cin >> A;
    const int n = A.size();
    dp[0][0][0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                for (int l = 0; l < 3; l++) {
                    for (int m = 0; m < 8; m++) {
                        int x = j ? 9 : A[i] - '0';
                        for (int d = 0; d <= x; d++) {
                            dp[i + 1][j || d < x][k || d == 3][(l + d) % 3][(m * 10 + d) % 8] += dp[i][j][k][l][m];
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
            for (int l = 0; l < 3; l++) {
                for (int m = 0; m < 8; m++) {
                    if ((k || l == 0) && m != 0) {
                        ans += dp[n][j][k][l][m];
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

最後の問題は yukicoder の世界のなんとか3とほとんど同じもの。

ある芸人は「3の倍数 もしくは 3のつく数」の時「アホ」になり、「8の倍数」の時「青春」するという。
A 以上 B 以下の整数のうち、「アホ」になりかつ「青春」しない数がいくつあるかを 109+7 で割った時の余りで求めてください。

$A$ 以上 $B$ 以下のものは($B$ 以下のもの)-($A$ 未満のもの)で求まるので、いままでの結果を使えば解けるね。引いて求める以外にも「$A$ より大きいことが確定している」というフラグを増やす方法もある。最近はそっちでやることがおおい。