Typical DP コンテストの桁DP

https://atcoder.jp/contests/tdpc/tasks/tdpc_number

• smaller の意味
  • $\mathrm{dp}[i][\text{smaller}=\mathrm{True}]$ = $N[0,i)$ 未満での場合の数
  • $\mathrm{dp}[i][\text{smaller}=\mathrm{False}]$ = $N[0,i)$ での場合の数 (0 か 1)
• 実装

その他

• ABC173 A - Neq Number

  

  (この図では0も neq number として扱っている)

• 各桁の和 (2) | アルゴ式

• ABC317 F - Nim

  • 3次元の桁DP？

• ABC465 E - Digit Circus

  • leading zero 考慮桁 DP のテンプレ問題

• 桁DPのオートマトンによる解釈 (32095 以下の整数を受理するオートマトン)

  • https://x.com/0x3b800001/status/1473517171242196992

• 桁DPはメモ化再帰を考えると比較的自然に生えてくる

  • 例えば $N= 63435$ の場合、以下のような場合分けをしたくなる
    • $[0, 6342]$ の末尾に $0$ から $9$ をつける
    • $6343$ の末尾に $0$ から $5$ をつける
  • こう考えると smaller が欲しくなる。