オートマトンと桁DP
桁DPは以下の図でだいたい説明できる。
0埋めDP（今命名）は以下の図。
この2つのDPの状態は独立しているので積が取れる（以下の表のNは上限）。
| 桁DP | 0埋めDP | 意味 |
|---|---|---|
| 0 | 0 | N = 0のときの0 |
| 0 | 1 | N > 0のときのN |
| 1 | 0 | N > 0のときの0 |
| 1 | 1 | 0 < D < Nを満たすすべての整数D |
1以上N未満の整数について知りたい場合は(1, 1)だけを参照すればいいし、0以上N以下の整数について知りたい場合は(0, 1), (1, 0), (1, 1)を参照すればいい。
桁DPの問題作り
けっこう簡単に作れる。
「0 ～ 9が与えられたときに状態が変化するもの」を付け加えればいい。
たとえば以下のようなもの。
- 3と7の出現回数が同じ
- すべての数字が偶数回出現
- 12345で割った余りが0
これらに「1以上N未満」みたいな条件を加えれば問題の完成。
- 1以上N未満の整数のうち、3と7の出現回数が同じものはいくつあるか
- 1以上N以下の整数のうち、すべての数字が偶数回出現するものはいくつあるか
- 0以上N以下の整数のうち、12345で割った余りが0のものはいくつあるか
問題の解法
今回は「1以上N未満の整数のうち、3と7の出現回数が同じものはいくつあるか」の問題を解いていく。
「1以上N未満の整数のうち」の部分は桁DPと0埋めDPで事足りるので一旦無視。「3と7の出現回数が同じものはいくつあるか」の部分だけ考える。これは更に2つの状態に分解できて、それは「3の出現回数」と「7の出現回数」である。
3の出現回数lのときに3を選択すればl + 1に遷移する。それ以外のときはlに遷移する。7も同様。
ここまでで4つのDPが出てきた。桁DP、0埋めDP、3の出現回数、7の出現回数。これらの状態をj, k, l, mとおき、遷移後の状態をj', k', l', m'とおく。遷移後の状態は次のようにして求められる。
| 状態 | 遷移 |
|---|---|
j' |
j = 0かつ選ぶ数字が桁の数字と同じなら0、j = 1または選ぶ数字が桁の数字未満なら1、それ以外なら遷移しない |
k' |
k = 0かつ選ぶ数字が0であれば0、それ以外なら1 |
l' |
選ぶ数字が3ならl + 1、それ以外ならl |
m' |
選ぶ数字が7ならm + 1、それ以外ならm |
ということで、C++のコードは次のようになる。
dp[0][0][0][0][0] = 1; rep(i, 20) rep(j, 2) rep(k, 2) rep(l, 20) rep(m, 20) rep(d, 10) { if (j == 0 && d > digit(N, 20 - i)) break; int _i = i + 1; int _j = j == 0 && d == digit(N, 20 - i) ? 0 : 1; int _k = k == 0 && d == 0 ? 0 : 1; int _l = d == 3 ? l + 1 : l; int _m = d == 7 ? m + 1 : m; dp[_i][_j][_k][_l][_m] += dp[i][j][k][l][m]; } long long ans = 0; rep(i, 20) ans += dp[20][1][1][i][i]; cout << ans << endl;
各状態の遷移を独立して考えると頭の中がオーバーフローしにくくなる。逆に、すべてを包括して考えてしまうと何が何だかわからなくなる（if文がネストしまくる）。
思ったこと
「状態を独立して考えられる」という考え方を数え上げDP以外のDPでも使えたらいいんだけど、どうなんだろう。そううまくはいかないかな。
