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

Benötigte Zeit

Problem A

Wenn es 1 ist, unterscheidet es sich von der Größe einer normalen Ganzzahl. Betrachten Sie es daher separat. (Ist es etwas komplizierter als das normale A-Problem?)

answerA.py

a,b=map(int,input().split())
if a==1 or b==1:
    print("Alice" if a==1 else "Bob" if b==1 else "Draw")
else:
    print("Alice" if a>b else "Bob" if a<b else "Draw")

B-Problem

Entscheiden Sie, welchem Pixel in A oben links in B entspricht, und rufen Sie die Funktion all_true auf (stellen Sie fest, ob alle Pixel übereinstimmen). (Ist das auch beim B-Problem etwas schwierig?)

answerB.py

n,m=map(int,input().split())
a=[list(input()) for i in range(n)]
b=[list(input()) for i in range(m)]
def all_true(i,j):
    global a,b
    for k in range(i,i+m):
        for l in range(j,j+m):
            if a[k][l]!=b[k-i][l-j]:
                return False
    return True
f=0
for i in range(n-m+1):
    for j in range(n-m+1):
        if all_true(i,j):
            f=1
            break
    if f==1:
        print("Yes")
        break
else:
    print("No")

C-Problem

Ich hatte das Gefühl, dass es schwierig sein würde, weil es ein Problem eines Musters ist, das ich noch nie gesehen habe, aber wenn ich mir die Einschränkungen anschaue, ist N maximal 8, also bestätige ich zuerst, dass ** es viel Zeit zum Ausführen gibt **. Wenn Sie in der Reihenfolge schreiben, in der die Scheitelpunkte besucht werden, werden hier alle Scheitelpunkte nur einmal besucht, sodass Sie sehen können, dass ** die Anzahl der im Pfad enthaltenen Scheitelpunkte genau N beträgt und alle unterschiedlich sind **. Außerdem ist die Anordnung von N verschiedenen Zahlen N! Und 8! Ist ungefähr $ 4 \ times10 ^ 4 $, so dass Sie sehen können, dass ** es scheint, dass Sie alle suchen können **. Ich denke, es gibt verschiedene Möglichkeiten, um zu überprüfen, ob jeder Pfad während einer vollständigen Suche vorhanden ist, aber hier verwenden wir eine benachbarte Matrix, weil wir sie wiederholt überprüfen **. Mit anderen Worten, bereiten Sie zuerst eine benachbarte Matrix vor, überprüfen Sie die Anordnung jedes Scheitelpunkts von vorne und prüfen Sie, ob zwischen jedem der beiden Scheitelpunkte ein Pfad vorhanden ist.

answerC.py

import itertools
n,m=map(int,input().split())
p=[[0]*n for i in range(n)]#Benachbarte Matrix
for i in range(m):
    a,b=map(int,input().split())
    p[a-1][b-1]=1
    p[b-1][a-1]=1
seq=(i for i in range(n))
x=list(itertools.permutations(seq))
#print(x[0])
l=len(x)
ans=0
for i in range(l):
    k=x[i]
    if k[0]==0:
        for j in range(n-1):
            if p[k[j]][k[j+1]]!=1:
                break
        else:
            ans+=1
            #print(k)
    else:
        break
print(ans)

D Problem

Als ich es zum ersten Mal sah, dachte ich, es sei unmöglich zu verstehen, aber die Verwendung von DP machte es einfacher als ich erwartet hatte. Der Grund für die Beurteilung, dass es sich um DP handelt, ist **, da die Reihenfolge keine Rolle spielt und daher nicht gierig genommen werden kann und die Methode zur Auswahl des Arzneimittels O ($ 2 ^ n ) ** ist. (Außerdem O ( N \ mal Summe (a) \ mal Summe (b) $), also habe ich bestätigt, dass es in das Zeitlimit passt.) Dieses Mal enthält ein Medikament jedoch zwei Substanzen, A und B, so dass es notwendig ist, ** DP in zwei Dimensionen ** zu verwenden. Mit anderen Worten, betrachten Sie einen DP, der eine Matrix erstellt, die die Menge von A und die Menge von B bei der Auswahl von N Chemikalien notiert und die Matrix aktualisiert. Danach mache ich einfach eine zweidimensionale Version von Knapsacks DP, daher denke ich, dass es schneller ist, den Code zu betrachten.

answerD.py

n,ma,mb=map(int,input().split())
el=[list(map(int,input().split())) for i in range(n)]
sa=sum(i[0] for i in el)
sb=sum(i[1] for i in el)

inf=1000000
#Mit inf initialisieren
x=[[inf for j in range(sb+1)] for i in range(sa+1)]
#Vergessen Sie nicht, das erste Element auf 0 zu setzen
x[0][0]=0
for i in range(n):
    now=el[i]
    #Bei der Verwendung von Deepcopy wurde es extrem langsam. Es ist jedes Mal schneller, ein normales Array zu erstellen
    x_sub=[[0 for j in range(sb+1)] for i in range(sa+1)]
    #x_Update auf Sub(Weil es nicht mehr als einen gibt)
    for k in range(sa+1):
        for l in range(sb+1):
            if x[k][l]!=inf and k+now[0]<sa+1 and l+now[1]<sb+1:
                x_sub[k+now[0]][l+now[1]]=x[k][l]+now[2]
    #x_Verschieben Sie den Wert von sub nach x
    for k in range(sa+1):
        for l in range(sb+1):
                if x_sub[k][l]!=0:
                    x[k][l]=min(x[k][l],x_sub[k][l])
mi=min(sa//ma,sb//mb)
ans=inf
#Denken Sie vom kleinsten zum kleinstmöglichen
for i in range(1,mi+1):
    ans=min(ans,x[ma*i][mb*i])
if ans==inf:
    print(-1)
else:
    print(ans)

Code, der konstant schneller ist

answerD_better.py

n,ma,mb=map(int,input().split())
el=[list(map(int,input().split())) for i in range(n)]
sa=sum(i[0] for i in el)
sb=sum(i[1] for i in el)
sa1=sa+1
sb1=sb+1

inf=1000000
x=[[inf]*(sb1) for i in range(sa1)]
x[0][0]=0
for i in range(n):
    now=el[i]
    x_sub=[[0]*(sb1) for i in range(sa1)]
    for k in range(sa1):
        for l in range(sb1):
            if x[k][l]!=inf:
                if k+now[0]<sa1:
                    if l+now[1]<sb1:
                        x_sub[k+now[0]][l+now[1]]=x[k][l]+now[2]
    for k in range(sa1):
        for l in range(sb1):
                if x_sub[k][l]!=0:
                    x[k][l]=min(x[k][l],x_sub[k][l])
mi=min(sa//ma,sb//mb)
ans=inf
for i in range(1,mi+1):
    ans=min(ans,x[ma*i][mb*i])
if ans==inf:
    print(-1)
else:
    print(ans)