[PYTHON] AtCoder Beginner Contest 104 Rückblick auf frühere Fragen
Benötigte Zeit
Impressionen
Es ist nicht gut, dass Sie das Problem im D-Level-Band nicht lösen können. ** Ich konnte meine Intelligenz nicht zusammenpressen, um Hinweise zu finden **. Ich werde versuchen, während des Wettbewerbs fest zu sein.
Problem A
Sie können es durch weniger als 1200 oder weniger als 2800 teilen. Mit dem ternären Operator ist das Schreiben einfach.
answerA.py
r=int(input())
print("ABC" if r<1200 else "ARC" if r<2800 else "AGC")
B-Problem
Obwohl es ein B-Problem war, war es ziemlich problematisch. Die zweite Bedingung kann leicht verarbeitet werden, aber die letzte Bedingung besteht darin, nur den relevanten Teil der Zeichenkette zu extrahieren und zu beurteilen, ob sie alle in Kleinbuchstaben geschrieben sind. Mit der Funktion islower () können Sie feststellen, ob sie niedriger ist.
answerB.py
s=input()
if s[0]=="A" and s[2:-1].count("C")==1:
if (s[1]+s[2:2+s[2:-1].index("C")]+s[s[2:-1].index("C")+3:]).islower():
print("AC")
else:
print("WA")
else:
print("WA")
C-Problem
Dieses Problem wurde schnell entschieden, aber ich habe einen dummen Fehler gemacht (** break-Anweisung wurde vergessen ** und ** Variable wurde falsch geschrieben **).
Wenn Sie normal darüber nachdenken, sollten Sie zunächst diejenigen mit der höchsten Grundpunktzahl auswählen. Abhängig von der Gesamtpunktzahl ändert sich jedoch der zu lösende Problempunkt **.
Hier konzentrierte ich mich auf die Tatsache, dass es nur D ($ \ leqq $ 10) Arten von Problemen gibt, und dachte, dass ** ich entscheiden sollte, welches Problem für jedes ** abgeschlossen werden soll **. Mit anderen Worten, Sie können alle Problemgruppen durchsuchen, die durch eine vollständige Bit-Suche abgeschlossen werden sollen.
Sobald Sie entschieden haben, welche Fragen zu beantworten sind, können Sie unter den Fragen, die Sie nicht auswählen, diejenigen mit der höchsten Punktzahl (✳︎) auswählen. Da das zu lösende Problem behoben ist, kann (✳︎) nicht abgeschlossen werden, und ** wenn Sie keinen G-Punkt oder höher erhalten, ohne ihn zu vervollständigen, müssen Sie das folgende Muster berücksichtigen **.
answerC.py
import math
d,g=map(int,input().split())
pc=[list(map(int,input().split())) for i in range(d)]
ans=10000000000000000000
for i in range(1<<d):
s=0
ans_=0
for j in range(d):
if (i>>j)&1:
s+=(pc[j][1]+pc[j][0]*100*(j+1))
ans_+=pc[j][0]
if s>=g:
ans=min(ans,ans_)
else:
for j in range(d-1,-1,-1):
if not((i>>j)&1):
if s+(pc[j][0]*100*(j+1))>=g:
h=-((s-g)//(100*(j+1)))
s+=(h*100*(j+1))
ans_+=h
ans=min(ans,ans_)
break
else:
break
print(ans)
D Problem
Zuerst dachte ich, dass ich nicht gut in Zeichenketten bin (vielleicht weil es viele DP-Muster gibt), aber am Ende hatte ich einen Schwanz ... ** Sie müssen Ihre Schwächen loswerden und das Problem angehen **….
Da die Anzahl der ABCs ** in der Reihenfolge (allmählich) von vorne nach A, B, C ** bestimmt werden kann, kann vermutet werden, dass DP verwendet werden kann (auch Experimente mit der Probe $ \ weil $). Machen). Da es schwierig ist, sofort an A → B → C zu denken, können Sie sich vorstellen, dass Sie sich getrennt für A → B und B → C entscheiden sollten (✳︎).
Daher können Sie (✳︎) verwenden, während Sie ** DP verwenden, wenn Sie es in den Zustand unterteilen, in dem ** A entschieden wird, den Zustand, in dem AB entschieden wird, und den Zustand, in dem ABC entschieden wird. Die Diskussion war bisher ziemlich gut, aber ich konnte die Verarbeitung eines Charakters nicht vollständig in Betracht ziehen.
In der Tat? Kann einfach ** A, B, C sein, indem alle drei Muster ausprobiert und addiert werden **. Tatsächlich ist auch ein Zustand, in dem nichts entschieden wurde, als Staat erforderlich. Fügen Sie diesen hinzu.
Aus der obigen Überlegung können wir erkennen, dass der folgende dp definiert werden sollte.
(Als ich DP definierte, hielt ich es für wichtig, zu verbalisieren, was jeder Zustand ist.)
Wenn Sie sich bisher entschieden haben **, können Sie über den Übergang nachdenken **. Es gibt viele Muster, in denen der Übergang $ dp [i] [j] = dp [i-1] [j] $ ist, aber das Muster nimmt zu, abhängig davon, ob das $ i $ -te Zeichen $ A, B oder C $ ist. Ich werde. Das heißt, wenn das i-te Zeichen A ist, muss das Muster von $ dp [i-1] [3] $ zu $ dp [i] [0] $ hinzugefügt werden, und wenn das i-te Zeichen B ist, muss das Muster hinzugefügt werden. Es ist notwendig, das Muster von $ dp [i-1] [0] $ zu $ dp [i] [1] $ hinzuzufügen, und wenn das i-te Zeichen C ist, $ dp [i] [2] $ zu $ Sie müssen das Muster von dp [i-1] [1] $ hinzufügen. Wenn das i-te Zeichen? Ist, gibt es außerdem Muster von A, B und C. Wenn Sie also alle addieren, ist $ dp [i] = [3 * dp [i-1] [0] + dp [i-1] [3], 3 · dp [i-1] [1] + dp [i-1] [0], 3 · dp [i-1] [2] + dp [i-1] [ Es wird 1], 3 * dp [i-1] [3]] $.
Dies reicht nicht aus, aber die folgende Abbildung kann das Beispiel der ersten Stichprobe erläutern (drei sind vertikal angeordnet, wenn? Ist A und B ist. Wenn es C.) war.
Das Obige ist implementiert und wird wie folgt. Es ist leicht, einen Fehler in dp [0] zu machen, daher müssen Sie vorsichtig sein.
✳︎ ** Da gierige Probleme und Teilstring-Probleme eine hohe Wahrscheinlichkeit für DP haben ** von früher **, möchte ich ruhig eine Richtlinie erstellen ** und ** über den tatsächlichen Übergang sorgfältig nachdenken ** Ich würde gerne vorsichtig sein.
answerD.py
mod=10**9+7
s=input()
l=len(s)
dp=[[0]*4 for i in range(l)]
for i in range(l):
if i==0:
dp[i][3]=1
if s[i]=="A":
dp[i][0]=1
elif s[i]=="?":
dp[i][0]=1
dp[i][3]=3
else:
if s[i]=="A":
dp[i]=[(dp[i-1][0]+dp[i-1][3])%mod,dp[i-1][1],dp[i-1][2],dp[i-1][3]]
elif s[i]=="B":
dp[i]=[dp[i-1][0],(dp[i-1][0]+dp[i-1][1])%mod,dp[i-1][2],dp[i-1][3]]
elif s[i]=="C":
dp[i]=[dp[i-1][0],dp[i-1][1],(dp[i-1][1]+dp[i-1][2])%mod,dp[i-1][3]]
else:
dp[i]=[(3*dp[i-1][0]+dp[i-1][3])%mod,(3*dp[i-1][1]+dp[i-1][0])%mod,(3*dp[i-1][2]+dp[i-1][1])%mod,(3*dp[i-1][3])%mod]
print(dp[-1][2])
Recommended Posts