ABC007D 禁止された数字 を解きました
⚓
これを解きました：ABC007D 禁止された数字
$A$ 以上 $B$ 以下の整数で、4と9のどちらかが少なくとも1つ以上含まれている数はいくつあるか。
$A, B$ は整数で、 $1\leqq A\leqq B\leqq 10^{18}$ 。 $10^4$ 以下の制約で部分点あり。
AtCode Problemを見ると、diffが1690もあるけど、たぶん古い問題だからなんだろうな。最近だと何回か出てるので、もっとdiffは低そう。
まず、よくある分解だけど、 $A$ 以上 $B$ 以下の整数でなんとかかんとか、っていう問題は、「 $0$ 以上 $B$ 以下」と「 $0$ 以上 $A-1$ 以下」に分けて考えるのがいい。前者から後者を引けば答え。
なので、結局、 $0$ 以上 $x$ 以下で、4か9が1つ以上入っている個数を数えればいい。
もちろん1個1個数えていくことはできないので、まとめて数える。桁だけ見ればいいので、桁ごとに見る。いわゆる桁dpを使う。
また、「どこかに現れる」より「どこにも現れない」のほうが考えやすいので、「4も9も現れない」を数えて全体から引くことを考える。
上の桁から見ていって、上のi番目までが上限と一致しているケースと一致していないケース（つまり小さいケース）にわける。
i+1番目まで一致しているケースは、i番目まで一致していて、さらにi+1番目が4でも9でもないケース。これを数えていく。
i+1番目まで見たときに一致していないケースは、i番目まで見たときにすでに一致してないケースと、i番目までは一致しているケース、がある。前者は、i+1番目は4と9以外なら何でもいい。後者は、i+1番目がより小さくなるように決めないといけない。i+1番目が2なら、「0,1」の2通り、i+1番目が5なら「0,1,2,3」の4通りなどとなる。
こうして漸化式ができるので、更新して全体から引けばOK。これを $B$ と $A-1$ に対して求めて、引けば答え。
個人的には、桁dpは、上の桁が上限と一致しているeqと一致していないlsとにわけて更新するのがわかりやすいと思っている。普通は、2次元配列にするんだろうけど。