[Python] Sumitomo Mitsui Trust Bank Programming Contest 2019 C (How to use DP) [AtCoder]

• This article is the basic of DP (Dynamic Programming) It is assumed that two Kaeru-kun problems can be solved.

• Frog1

• Frog2

It melts in DP! !! !! There was a problem that impressed me, so I will write it as an article. I know the idea of DP, but it doesn't connect with the actual problem! May be helpful (maybe not w)

Sumitomo Mitsui Trust Bank Programming Contest 2019C

Difficulty:205 After reading the problem, a full bit search and a 6-fold for statement crossed my head for a moment, but it seems to be useless.

By the way, you can solve it even if you can't think of DP. (I will post it as a separate solution at the end of the article.) But if you can't think of a DP I think it will take about 15 minutes to find the law.

** Fast solution is essential to raise the rate! ** **

Benefits of DP

The good thing about DP is (not limited to DP) The moment I realized that "this problem can be solved with DP!" ** I can code with almost brain death ** thing! Then ** I don't put my thoughts in there **, so I think that this level of problem will be able to aim for AC in about 5 minutes!

** The point is whether you realize that you can use DP! ** **

Let's consider a concrete example

Anyway, prepare a notebook and a pen, Let's think about OK pattern and NG pattern.

1~99：NG 100,101,102,103,104,105：OK 106~199：NG 200,201,202,203,204,205,206,207,208,209,210：OK 211~299：NG 300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315：OK ...

Why is 200 ~ 205 OK? That's because 100 ~ 105 is added to 100 which is OK originally. Why is 201 ~ 206 OK? That's because 100 ~ 105 is added to 101 which is OK originally. I see! Then, if you add 100 ~ 105 to each of the originally OK 200 ~ 210, it seems to be OK.

Oh, I think I can go with DP! If you accept 0 yen as OK, add 100 ~ 105 to 0, which is originally OK, and it will be OK! It looks like it will work! All you have to do is code! !! !!

answer

If you think about the Index number of DPMap for a moment, you should be able to die of brain death! Also, if you know that it's DP the moment you read the problem, you won't need a notebook and pen!

test.py

def I(): return int(input())
X = I()
dp = [0]*(X+1) #0_indexed
dp[0] = 1 #I'll accept 0 yen as OK!
for i in range(X+1):
    if dp[i]:
        for j in range(100,106):
            if i+j<=X: #Measures for "out of lange".
                dp[i+j] = 1
print(dp[-1])

Estimated whether DP can be used

When the next concrete example can be derived from the previous value when giving concrete examples in order → It seems worth considering whether DP can be used! !! !!

Another solution

I didn't notice DP at first glance, so I did it here. The amount of code is small, but I think it will take some time to derive this code. (I wonder if this is faster for those who are accustomed to finding such a law)

test.py

def I(): return int(input())
X = I()
a,b = divmod(X,100)
print(1 if a*5>=b else 0)

end!