※この記事は、DP(動的計画法)の基本中の基本である
かえるくん問題2問がとけることを前提としています。

Frog1

Frog2

DPでとけるんだ！！！
と感動した問題がありましたので記事にします。
DPの考え方は知っているけれども、実際の問題と結びつかない！
という人は参考になるかも(ならないかもw)

三井住友信託銀行プログラミングコンテスト2019C

Difficulty:205
問題を読んで、bit全探索や6重for文が一瞬頭をよぎりましたがダメそう。

ちなみにDPが思いつかなくても解けます。(記事の最後に別解として載せておきます。)
しかしDPが思いつかなかった場合、
たぶん法則性をみつけるのに15分くらいかかる気がします。

レートをあげるには早解きが必須！

DPのメリット

DPのいいところは、(DPに限らずの話ですが)
「この問題、DPで解ける！」と気づいた瞬間、ほぼ脳死でコーディングできる
こと！
するとそこに思考を挟まないので、
このレベルの問題は5分くらいでACを目指せるようになると思います！

DPを使えることに気付けるかどうかがポイント！

具体例を考えよう

とにもかくにもノートとペンを用意して、
OKパターン・NGパターンを考えましょう。

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

なぜ200~205がOKなのか？
それは、もともとOKの100に100~105を足しているから。
なぜ201~206がOKなのか？
それは、もともとOKの101に100~105を足しているから。
なるほど！
ではもともとOKの200~210それぞれに対して100~105を足せば、それもOKになりそう。

あ、DPでいけそう！
0円をOKとしてやれば、もともとOKの0に100~105を足してOKとなる！
うまくいきそう！
あとはコーディングするだけ！！！

答え

DPMapのIndex番号だけちょっと考えれば、あとは脳死でいけるはず！
また、問題を読んだ瞬間にDPだとわかればノートとペンも必要なさそう！

test.py

def I(): return int(input())
X = I()
dp = [0]*(X+1) #0_indexed
dp[0] = 1 #0円をOKとしてやる！
for i in range(X+1):
    if dp[i]:
        for j in range(100,106):
            if i+j<=X: #「out of lange」対策。
                dp[i+j] = 1
print(dp[-1])

DPを使えるかどうかの目安

具体例を順番にあげていくときに、前の値から次の具体例を導き出せる場合
→DPが使えるかどうか考えてみる価値がありそう！！！

別解

俺は初見でDPと気づかなかったのでこっちでやりました。
コード量は少ないけど、このコードを導くのに時間がかかると思います。
(こういう法則を見つけるのに慣れてる人はこっちの方が早いのかなぁ)

test.py

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

おわり！