ARC1173A - Neq Numberが全く解けなかったので。
自分にとっての初出はABC-E Digit Sum Divisibleだったけど、時間の都合で放置を重ねて忘れており、流石に良くないのでまとめてみる。
参考
気持ち
「あるKが与えられる。X<KであるXのうち、~な条件を満たす最大値・個数を求めよ」
という競プロ典型問題を高速に解くことができるDP。
例えば、「8357よりも小さい非負整数の数」を求める。
f(x, y) = x以上y未満の非負整数の数とすると、
f(0, 8357) = f(0, 8000) + f(8000, 8300) + f (8300, 8350) + f (8350, 8357)
である。この分割をDPに落とし込んだのが桁DP。
実装面で考える
基本実装では
dp[ i ] := 上から i 桁目まで決めたときの暫定スコア
と定義する。
ただし、今回のARC173Aで例えば23以下のNeqNumberの数を求めたいとなったときに、1桁目に1が入るケースと2が入るケースで後ろに入れれる値が変わる場合がある。そういうときは、横10(0~9)の二次元DPにするなり、まぁ問題によって対応すれば良い。