tooh’s diary

半角全角、常体敬体が入り乱れるカオス

桁DP

桁DPは、例えば「0以上N以下の数字で、ある条件を満たす数字がいくつあるか」などを数えるのに便利な手法である。

発想が単純なものと、複雑なものの2パターンある。

<単純な方>
例えばこの問題↓
atcoder.jp

?はワイルドカード(0~9のいずれでもいい)の時、?5?という形をしている3桁の数字で、13で割って5余るような数字はいくつ存在するかを数える。

上から順に数字を見ていく。まず、「n桁目を見たところまでで、13で割って5余る数字は何通りか?」を管理するために、「n桁目を見たところまでに13で割ってi余る数字」をdp[i]とする配列dpを考える。

例えば?5?であれば、一番左(最初)の桁が?なので、dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]となる。(?には0~9が入るため、ここまでを13で割った結果がdpになる)
次に、真ん中の桁が5になるので、?5を13で割った余りは、dp = [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1]となる。(例えば、dp[2]について、25を13で割った余りは12になるので、もともとdp[2]にあった1はdp[12]に移る)
最後に、一番右の桁が?なので、dp = [8, 8, 7, 8, 8, 8, 7, 8, 8, 8, 7, 7, 8]となる。dp[5]は、すべての0~12のiについて、(10*i+j) % 13 == 5となるようなj(つまりワイルドカードの?)を試し、その場合の数を加算してあげればいい。

その他の例
atcoder.jp


<複雑な方>

例えば「N以下で4の入った数字はいくつありますか?」という問いかけで、N=50であれば、十の位を1~9まで全部見ても、十の位で弾けるから簡単だが、N=1234とかだった場合に、千の位が1だった時に、単純にdpを作ろうと思っても「1100」と「1200」で扱いが変わってきたりする。(前者は十の位がなんでもいいけど、後者だと十の位の動きに制限が出る)

そういうのを管理するために、単純なdpではなく、
dp[今見ている桁][Nよりも明らかに小さいか、同じか][すでに4が登場しているか]
という配列で管理するのが良い。これを用いて遷移を場合分けしていけばいいんだけど、かなり面倒。

atcoder.jp

abc007.contest.atcoder.jp

atcoder.jp