[Python] Sumitomo Mitsui Trust Bank Programmierwettbewerb 2019 C (Verwendung von DP) [AtCoder]

• Dieser Artikel ist die Grundlage von DP (Dynamic Planning). Es wird angenommen, dass zwei Kaeru-Kun-Probleme gelöst werden können.

• Frog1

• Frog2

Es schmilzt in DP! !! !! Es gab ein Problem, das mich beeindruckt hat, deshalb werde ich es als Artikel schreiben. Ich kenne die Idee von DP, aber sie hängt nicht mit dem eigentlichen Problem zusammen! Kann hilfreich sein (vielleicht nicht w)

Programmierwettbewerb der Sumitomo Mitsui Trust Bank 2019C

Difficulty:205 Nachdem ich das Problem gelesen hatte, kam mir für einen Moment eine vollständige Bit-Suche und ein 6-facher Satz in den Sinn, aber es scheint nutzlos zu sein.

Übrigens können Sie es lösen, auch wenn Sie nicht an DP denken können. (Ich werde es als separate Lösung am Ende des Artikels veröffentlichen.) Aber wenn Sie nicht an einen DP denken können Ich denke, es wird ungefähr 15 Minuten dauern, bis das Gesetz gefunden ist.

** Eine schnelle Lösung ist wichtig, um die Rate zu erhöhen! ** ** **

Vorteile von DP

Das Gute an DP ist (nicht auf DP beschränkt) In dem Moment wurde mir klar, dass "dieses Problem mit DP gelöst werden kann!" ** Ich kann mit fast Hirntod codieren ** Ding! Dann ** lege ich meine Gedanken nicht hinein **, also Ich denke, dass dieses Problem in etwa 5 Minuten auf Wechselstrom abzielen kann!

** Der Punkt ist, ob Sie erkennen, dass Sie DP verwenden können! ** ** **

Betrachten wir ein konkretes Beispiel

Wie auch immer, bereiten Sie ein Notizbuch und einen Stift vor, Lassen Sie uns über das OK-Muster und das NG-Muster nachdenken.

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

Warum ist 200 ~ 205 OK? Das liegt daran, dass "100 ~ 105" zu "100" hinzugefügt wird, was ursprünglich in Ordnung ist. Warum ist "201 ~ 206" in Ordnung? Das liegt daran, dass "100 ~ 105" zu "101" hinzugefügt wird, was ursprünglich in Ordnung ist. Das war's! Wenn Sie dann "100 ~ 105" zu jedem der ursprünglich OK "200 ~ 210" hinzufügen, scheint dies in Ordnung zu sein.

Oh, ich denke ich kann mit DP gehen! Wenn Sie 0 Yen als OK akzeptieren, fügen Sie "100 ~ 105" zu "0" hinzu, was ursprünglich in Ordnung ist, und es wird in Ordnung sein! Es sieht so aus, als würde es funktionieren! Alles was Sie tun müssen, ist Code! !! !!

Antworten

Wenn Sie nur an die Indexnummer von DPMap denken, sollten Sie in der Lage sein, an Gehirn zu sterben! Wenn Sie wissen, dass es DP ist, sobald Sie das Problem lesen, benötigen Sie kein Notizbuch und keinen Stift!

test.py

def I(): return int(input())
X = I()
dp = [0]*(X+1) #0_indexed
dp[0] = 1 #Ich akzeptiere 0 Yen als OK!
for i in range(X+1):
    if dp[i]:
        for j in range(100,106):
            if i+j<=X: #Maßnahmen für "out of lange".
                dp[i+j] = 1
print(dp[-1])

Geschätzt, ob DP verwendet werden kann

Wenn das nächste konkrete Beispiel aus dem vorherigen Wert abgeleitet werden kann, wenn konkrete Beispiele in der richtigen Reihenfolge angegeben werden → Es scheint eine Überlegung wert zu sein, ob DP verwendet werden kann! !! !!

Eine andere Lösung

Ich habe DP auf den ersten Blick nicht bemerkt, also habe ich es hier gemacht. Die Menge an Code ist gering, aber ich denke, es wird einige Zeit dauern, diesen Code abzuleiten. (Ich frage mich, ob dies für diejenigen, die es gewohnt sind, ein solches Gesetz zu finden, schneller ist.)

test.py

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

Ende!