[PYTHON] AtCoder Beginner Contest 113 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

"D Problem ist schwierig, ich weiß nicht!", Aber als ich es überprüfte, war es ein DP, der nichts war. Ich habe in letzter Zeit viele Fehler gemacht, dass ich aufgrund des Problems des Staatsübergangs nicht auf die Idee der DP kommen kann, deshalb werde ich es das nächste Mal nie tun.

Problem A

y ist der halbe Preis.

answerA.py

x,y=map(int,input().split())
print(x+y//2)

B-Problem

Die Zahl, die A am nächsten kommt, ist die Zahl mit der kleinsten absoluten Differenz zu A. Da Sie nach der Punktnummer suchen, müssen Sie auch die Punktnummer speichern.

answerB.py

n=int(input())
t,a=map(int,input().split())
h=[t-int(i)*0.006 for i in input().split()]
ans=[-1,1000000000]
for i in range(n):
    if abs(h[i]-a)<abs(ans[1]-a):
        ans=[i,h[i]]
print(ans[0]+1)

C-Problem

Die Ausgabe ist eine Kombination aus der Nummer der Präfektur, zu der Sie gehören, und der Anzahl der Geburten in dieser Stadt. Daher ist es zunächst notwendig, die Stadt nach Präfekturen zu teilen. Da es notwendig ist, in der Reihenfolge auszugeben, die am Ende ursprünglich durch Eingabe empfangen wurde, teilen Sie es in Arrays für jede Stadt auf und geben Sie einen Satz des Geburtsjahres und der Reihenfolge ein, die von der ersten Eingabe in jedem Array empfangen wurde. .. Ordnen Sie darunter die Anordnung für jede Präfektur in der Reihenfolge ihrer Geburt an, kombinieren Sie sie mit der Präfekturnummer und fügen Sie sie zusammen mit der Reihenfolge, die bei der ersten Eingabe und bei der letzten Ausgabe eingegangen ist, in das Ausgabearray ein. Sie können in der Reihenfolge ** ausgeben, die bei der ersten Eingabe ** eingegangen ist.

answerC.py

n,m=map(int,input().split())
pyi=[[] for i in range(n)]
for i in range(m):
    p,y=map(int,input().split())
    pyi[p-1].append([y,i])
ans=[]
for i in range(n):
    pyi[i].sort()
    for j in range(len(pyi[i])):
        ans.append([(6-len(str(i+1)))*"0"+str(i+1)+(6-len(str(j+1)))*"0"+str(j+1),pyi[i][j][1]])
ans.sort(key=lambda x:x[1])
for i in range(m):
    print(ans[i][0])

D Problem

Zuerst habe ich versucht, mit bfs und dfs nach Mida zu suchen, aber ich weiß nicht, wie ich die Anordnung horizontaler Linien bestimmen soll, die nicht ** und ** verlaufen, da die Berechnung nicht rechtzeitig erfolgen kann, da sie mehr als ** $ 10 ^ 9 + 7 $ betragen kann. ** Also habe ich aufgegeben. Da Amidakuji sich von oben nach unten bewegt, ist die Idee, dass ** es möglich ist, eine schrittweise Formel zu formulieren, indem man sich von oben nach unten bewegt ** (ich hatte diese Idee). ** DP ** ist am besten mit der schrittweisen Formel kompatibel, und wir werden eine Richtlinie mit DP in Betracht ziehen. Nehmen wir nun an, Sie befinden sich auf der vertikalen Linie an der Position von X cm von oben und überlegen, zu welcher horizontalen Linie Sie sich an der Position von X + 1 cm bewegen können. Dann ** können Sie nur zur nächsten horizontalen Linie ** und nicht zu einer weiter entfernten horizontalen Linie wechseln. Da wir wissen, wie man sich bewegt, sei das Element von dp dp [X] [i] und die Zahl **, wenn es sich an der Position der i-ten vertikalen Linie von links in ** Xcm (0-indiziert) befindet. Außerdem wird dp [x + 1] [i] nur aus dp [x] [i-1], dp [x] [i], dp [x] [i + 1] bestimmt. Hier möchte ich eine Kombination von ** nicht passierenden (irrelevanten) horizontalen Linien ** betrachten, wenn ich die horizontalen Linien kenne, die in Xcm verlaufen, aber ich fand es schwierig, die passierenden horizontalen Linien und die nicht passierenden horizontalen Linien getrennt zu betrachten. Es war. Beachten Sie daher, dass w extrem klein ist (w $ \ leqq $ 8) und dass ** alle horizontalen Linienkombinationen bei einer vollständigen Suche berücksichtigt werden können **, die Bedingung (beide horizontalen Balken teilen sich einen Endpunkt). Betrachten Sie alle Kombinationen horizontaler Linien, die erfüllen (nicht), und wenn die horizontalen Linien mit i-1 → i verbunden sind, fügen Sie dp [x] [i-1] zu dp [x + 1] [i] und i + 1 → i hinzu Wenn die horizontale Linie mit verbunden ist, addiere dp [x] [i + 1] zu dp [x + 1] [i], und wenn weder die horizontale Linie von i-1 → i noch die horizontale Linie von i + 1 → i verbunden sind Wenn Sie dp [x] [i] zu dp [x + 1] [i] hinzufügen, können Sie DP mit O ($ HW2 ^ W $) ausführen. Und da der zu erreichende vertikale Balken K ist (K-1, wenn er 0-indiziert ist), können Sie dp [H] [K-1] finden.

answerD.py

mod=10**9+7
h,w,K=map(int,input().split())
dp=[[0]*w for j in range(h+1)]
dp[0][0]=1
for i in range(1,h+1):
    for k in range(2**(w-1)):
        for l in range(w-2):
            if ((k>>l)&1) and ((k>>(l+1))&1):
                break
        else:
            for l in range(w):
                if l==0:
                    if ((k>>l)&1):
                        dp[i][l+1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
                elif l==w-1:
                    if ((k>>(l-1))&1):
                        dp[i][l-1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
                else:
                    if ((k>>l)&1) or ((k>>(l-1))&1):
                        if ((k>>l)&1):
                            dp[i][l+1]+=dp[i-1][l]
                        else:
                            dp[i][l-1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
print(dp[h][K-1]%mod)