[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.

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!

Recommended Posts

[Python] Sumitomo Mitsui Trust Bank Programming Contest 2019 C (How to use DP) [AtCoder]
AtCoder Sumitomo Mitsui Trust Bank Programming Contest 2019 Participation Report
Sumitomo Mitsui Trust Bank Programming Contest 2019 Review
python3: How to use bottle (2)
Atcoder Acing Programming Contest Python
[Python] How to use list 1
How to use Python argparse
Python: How to use pydub
[Python] How to use checkio
[Python] How to use input ()
How to use Python lambda
[Python] How to use virtualenv
python3: How to use bottle (3)
python3: How to use bottle
How to use Python bytes
[Python] Technique to reduce dimensions with DP (Dynamic Programming) [AtCoder]
Python: How to use async with
[Python] How to use Pandas Series
How to use Requests (Python Library)
How to use SQLite in Python
[Python] How to use list 3 Added
How to use Mysql in python
How to use OpenPose's Python API
How to wrap C in Python
How to use ChemSpider in Python
How to use FTP with Python
Python: How to use pydub (playback)
How to use PubChem in Python
How to use python zip function
[Python] How to use Typetalk API
AtCoder Beginner Contest 174 C Problem (Python)
atcoder Review of Panasonic Programming Contest 2020, up to question E (Python)
[Python] Summary of how to use pandas
[Introduction to Python] How to use class in Python?
How to install and use pandas_datareader [Python]
How to use Google Test in C
[Python] [Explanation] AtCoder Typical DP Contest: A Contest
[python] How to use __command__, function explanation
[Python] How to use import sys sys.argv
[Python] Organizing how to use for statements
Memorandum on how to use gremlin python
[Python2.7] Summary of how to use unittest
python: How to use locals () and globals ()
How to use __slots__ in Python class
How to use "deque" for Python data
How to use Python zip and enumerate
[Python] Understand how to use recursive functions
Summary of how to use Python list
How to use regular expressions in Python
[Python2.7] Summary of how to use subprocess
How to use is and == in Python
[Blender x Python] How to use modifiers
AtCoder Beginner Contest 167 B Problem "Easy Linear Programming" Explanation (Python3, C ++, Java)
[Question] How to use plot_surface of python
How to enjoy programming with Minecraft (Ruby, Python)
[Python] How to use two types of type ()
[Introduction to Udemy Python3 + Application] 23. How to use tuples
How to generate permutations in Python and C ++
Study from Python Hour7: How to use classes
How to use Raspberry Pi pie camera Python
How to use Python Image Library in python3 series