ABC007 D - 禁止された数字

D - 禁止された数字

提出コード
問題をぱっと見て桁DPっぽいなーと思ったので桁DPをやります。
A-1、もしくはB以下の、4または9が含まれている数の個数をそれぞれ桁DPで調べて、最後にB以下の個数からA-1以下の個数をひいてあげれば答えになります。
dp[i][j][k]とします。
i:今現在見ている桁(上からi桁目)
j:与えられた数字(A-1,もしくはB)を下回っていることが確定しているかどうか(していたら1)
k:4および9が含まれているかどうか(含まれていたら1)
とします。
jについてですが、下回っていることが確定している、というのは以下のようになります。
例えばBが2345という数字であったとき、上から2桁を
00~22の中のいずれかにした場合、jは1になります(それ以下の桁は0~9の何を選んでもBを下回るからです)。
23のとき、次の桁は0~4のいずれかを選ばないといけないのでjは0になります。
24以上のときは、そもそも考慮してはいけないので考えません。
次に、DPの遷移についてです。そこそこの種類が存在します。
初期状態はdp[0][0][0]=1でそれ以外は0です。
今、i桁目の数字をpという数字にしようと考えているとします(pは0~9のいずれかになります)。ここから場合分けをしていきます。6通りあります。
A-1、もしくはBのi桁目を、s[i]とします。

pが4、もしくは9であった場合

この中でさらに3通りに分けることができます。
s[i]とpを比較したときにどちらが大きいか、です。

• p<s[i]だった場合
  この時点で、jはいかなる数字でも1になります。
  そして、pが4もしくは9であるので、kもすべて1になります。なので
  dp[i][1][1] += dp[i-1][j][k](j,kは0,1の両方であるとします)
  となります。

• p=s[i]だった場合
  kすべては1になりますが、jは一つ前のi-1の状態をそのまま引き継ぎます。
  dp[i][j][1] += dp[i-1][j][k](jは、0,1が両辺で一致してないといけません。kはどちらでもいいです)

• p>s[i]だった場合
  kはすべて1になります。
  すでにjが1であればその個数を引き継ぐことができますが、jが0のものは引き継ぐことができません。よって次のようになります。
  dp[i][1][1] += dp[i-1][1][k]

pが4でも9でもない場合

こちらも先ほどと同様に3つの場合わけを行います。kのパターンが少し変化するだけで、基本的には一緒です。

• p<s[i]だった場合
  dp[i][1][k] += dp[i-1][j][k]

• p=s[i]だった場合
  dp[i][j][k] += dp[i-1][j][k]

• p>s[i]だった場合
  dp[i][1][k] += dp[i-1][1][k]

あとは、これをもとに、pを0~9までループ、そしてiを最初の桁から最後の桁までループして、A-1以下、B以下の、条件を満たす数の個数を調べ上げて引き算をすれば答えが求まります。