ABC154E

https://gyazo.com/3144c591c48ca98ba526eb541f2ade6d

考えたこと

100桁についてゼロでない数値の出現回数3のテーブルでDP

桁DPとは

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

上位i桁について既知の時にそれを使ってi+1桁の場合を求める

今回の場合なら上位i桁でゼロでない数字をk個つかう場合の和がxなら、0を末尾につけたらkのままi+1桁になる、1〜9ならk+1になる

ただし上位i桁がNと一致してる場合だけは例外で、1〜9ではNを超える可能性があるのでNのi+1桁目の値をケアする必要がある

code:python

def solve(N, K):

equal = 0

for v in N:

if v != 0 and equal <= K:

equal += 1

for k in range(K + 1):

less = new_less

if equal == K:

ret += 1

return ret

AC