ABC154-E (digit DP) in Python

problem

Understand and show ABC154-E!

Total number

First, the total number of numbers less than or equal to N is calculated using the digit DP. Consider 314159. For example, if you have decided up to 313, any number below that is allowed. On the other hand, if the rule is 314, only 0 or 1 is allowed under one. In other words, it is necessary to have information on which digit to decide and whether less than N is decided by the decision method. ** dp [i] [j]: Determine up to the i-th digit, j = 1 if less than N is confirmed, j = 0 ** if it matches N To be determined. Since the initial value matches N at this point using up to the 0th digit dp[0][0] = 1 And. After that, the number of digits is increased, but for the next digit, the number that matches N is always 1 (same as the previous one), and the number less than N is 0 for the one that is confirmed to be less than N one before. The recurrence formula is as follows because it is the product of ~ 9 multiplied by 10 and the one equal to the previous N multiplied by 0 ~ the number of digits-1. dp[i][0] = dp[i - 1][0] dp[i][1] = dp[i - 1][1] * 10 + dp[i - 1][0] * int(str(N)[i - 1])

code

N = input()
m = len(N)
dp = [[0] * 2 for _ in range(m + 1)]
dp[0][0] = 1

for i in range(1, m + 1):
    dp[i][0] = dp[i - 1][0]
    dp[i][1] = dp[i - 1][1] * 10 + dp[i - 1][0] * int(N[i - 1])

ans = dp[m][0] + dp[m][1]

print(ans)

Total number of N or less, including K non-zero numbers

** dp [i] [j] [k]: Added condition to include k non-zero numbers ** Let l be the number in the i-th digit dp[i][0][k] = dp[i - 1][0][k] * (l == 0),dp[i - 1][0][k - 1] * (l != 0) dp[i][1][k] = dp[i - 1][1][k] + dp[i - 1][1][k - 1] * 9 + dp[i - 1][0][k] * 1 * (l != 0) + dp[i - 1][0][k - 1] * (l - 1) * (l != 0) I think it will be, but please tell me because it seems to be wasteful> <

Way of thinking

dp [i] [0] [k]: If l is 0, then k remains the same to match the given number, so dp [i -1] [0] [k], otherwise Sometimes the non-zero number increases by one, so dp [i -1] [0] [k -1].

dp [i] [1] [k]: First, one from dp [i -1] [1] [k] whose next digit is not 0, dp [i -1] [1] [k -1] The next digit is 9 from 1 to 9. Next, if l is not 0, dp [i -1] [0] [k] with the next digit as 0 becomes dp [i -1] with the next digit as 1 ~ (l -1). ] [0] [k -1] transitions by l -1. (Difficult to understand cedar)

code

N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1):
        dp[i][1][k] += dp[i - 1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i - 1][0][k]
        else:
            dp[i][0][k] += dp[i - 1][0][k]
        if k - 1 >= 0:
            dp[i][1][k] += 9 * dp[i - 1][1][k - 1]
            if l != 0:
                dp[i][0][k] += dp[i - 1][0][k - 1]
                dp[i][1][k] += (l - 1) * dp[i - 1][0][k - 1]

print(dp[m][0][K] + dp[m][1][K])

Afterword

Please give me some advice. .. .. .. I will answer as many questions as I can. .. .. ..

References

Introduction to Digit DP

Recommended Posts

ABC154-E (digit DP) in Python
Solve ABC160-E in Python
Quadtree in Python --2
Python in optimization
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Unittest in python
[Python] DP ABC184D
Epoch in Python
Discord in Python
Sudoku in Python
nCr in python
N-Gram in Python
Programming in python
Plink in Python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
N-gram in python
LINE-Bot [0] in Python
Csv in python
Disassemble in Python
Reflection in Python
Constant in python
nCr in Python.
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Quad-tree in Python
Reflection in Python
Chemistry in Python
Hashable in python
DirectLiNGAM in Python
LiNGAM in Python
Flatten in python
flatten in python
Ant book in python: Sec. 2-3, Dynamic Programming (DP)
Sorted list in Python
Daily AtCoder # 36 in Python
Daily AtCoder # 2 in Python
Implement Enigma in python
Daily AtCoder # 32 in Python
Daily AtCoder # 18 in Python
Singleton pattern in Python
File operations in Python
Key input in Python
Daily AtCoder # 33 in Python
Logistic distribution in Python
Daily AtCoder # 7 in Python
LU decomposition in Python
One liner in Python
Daily AtCoder # 24 in Python
case class in python
RNN implementation in python
Daily AtCoder # 8 in Python