桁DP

巨大な整数Nが与えられてN以下の非負の整数から条件を満たすものの数を数え上げる時に使える動的計画法アルゴリズム

自分の実装例

• DP S 1以上K以下の整数のうち、十進表記における各桁の数字の総和が Dの倍数

• ABC154E 1以上 N以下の整数であって、 10進法で表したときに、0でない数字がちょうど K個

• 上位i桁についての情報を使ってi+1桁の場合の情報を求める

  • ABC154E: 上位i桁でゼロでない数字をk個つかう場合の数がxとする。
    • 次の一桁が0の時はkのまま、x通り。1〜9ならk+1になる、9x通り。

python

for k in range(K + 1):
    new_less[k] += less[k]  # for 0
    new_less[k + 1] += 9 * less[k]  # for 1..9

• ただし上位i桁がNと一致してる場合だけは例外

  • 1〜9ではNを超える可能性がある
  • Nのi+1桁目の値をケアする必要がある
    • 上位i桁がNと一致してる数は常に1通りなので、配列ではなく値で持っている
    • 世の中の解説ではこれも配列にするものがあるが、今のところそれが必要な問題に出会ったことがない

• 最後にNに一致する場合が条件を満たすなら回答+1する

• 自然に実装すると「0以上の整数」についての値になるので問題条件によっては0の場合を引く

• Digit DP 入門 - torus711 のアレ

• https://atcoder.jp/contests/abc154/tasks/abc154_e

https://maspypy.com/atcoder-参加感想-2019-02-16abc-155

DIgit DP 動的計画法