桁DP
テンプレ
自分は上から走査してisSmallerフラグを持つやつでやりがち。
遷移前後のisSmallerフラグの組み合わせは以下3パターン(1度「未満」になったら「丁度」に遷移することはない)
true → true
どの数字でもOK
false → true
i桁目の数字よりも小さければ「未満」に遷移する。
気を抜くと0の引き忘れや不等号の向き誤りでバグらせがち。
rep(j, 10) if (j < N[i] - '0')
false → false
i桁目の数字と同じなら「丁度」のまま。
rep(j, 10) if (j == N[i] - '0')
典型
桁和の最大値(桁DPしない解法が一般的だけど)
$ dp[0][1] からは遷移しないことに注意する。
桁和がDの倍数となる個数。
this is ド典型。
求める値は1以上だけどdp上は0の場合もカウントされるので引く。
10進数表記でDの倍数となる個数。
遷移後のmodの計算で桁数を考慮する必要がある
(遷移前のmod) + 10^(右から見た0-indexed桁数) * (今の桁の数字)
0がないのでleading-0(e.g. 07)のパターンを明示的に書く必要があることに注意する
1桁目は自動的に扱えるのでよい
2桁目以降は「未満」のテーブルをインクリメントすればよい
他の実装として、「ここまで0が続いている」というフラグも持つ方針があるが、この問題では明らかに常に1パターンなので要らんそう
Digit Sumと完全に同じなので略。
ARC-Aっぽい。桁DPではないので略。
0でない数字がK個になる個数。
特段躓くポイントのない桁DP入門(diff 1298)
isSmallerを考慮しなくていいので桁DP固有っぽさはないDP(diff 1334)
i桁目までの余りがjで、i+1桁目をkとする時
提出1:j + k * 10^(右から何桁目か)
正当性は明らか
前計算して配列を用意するか、10^m mod Pを誤差なく高速に計算できるようにする
提出2:j * 10 + k
正当性は桁数の回数分10が掛けられることから示せる
計算は簡単
提出2を使いましょうという学び。
解説解は各桁ごとに算数する(diff 試験管1393)
桁DPで解くなら $ dp[i][num1][isSmaller] := i桁目までで1をnum1個書くような値の個数 を数え上げて最後に1を書いた数を係数として総和を取れば求まる。
二進数での桁DP(diff 1423)
isSmallerフラグだけ持てば貪欲に決められるので陽にDP配列を持つ必要はない(自分も初見ではそう解いていたらしい)が、DPで機械的に処理できるならDPするのが速解きの真髄。
$ dp[i][isSmaller]:= i桁目まで決めた時の最大値
-INFで初期化して$ dp[0][1] などから遷移しないように気を付ける
最大値系の桁DP典型
整数型を2進数の文字列に変換 string K = bitset<60>(Knum).to_string();
(bitsetを使うなら文字列にしなくてもいいけど手癖)
TODO:解く
TODO:読む
TODO:メモ化再帰実装