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

D zum ersten Mal gelöst

Benötigte Zeit

Problem A

Vergleiche Vorder- und Rückseite

answerA.py

a,b,c=input().split()
if a[-1]==b[0] and b[-1]==c[0]:
    print("YES")
else:
    print("NO")

answerA_better.py

a,b,c=input().split()
print("YES" if a[-1]==b[0] and b[-1]==c[0] else "NO")

B-Problem

Ich hatte einen Fehler im Kopf und dachte ungefähr 10 Minuten darüber nach.

answerB.py

import fractions
a,b,c=map(int,input().split())
d=fractions.gcd(a,b)

if c%d==0:
    print("YES")
else:
    print("NO")

answerB_better.py

import fractions
a,b,c=map(int,input().split())
d=fractions.gcd(a,b)
print("YES" if c%d==0 else "NO")

C-Problem

Ich dachte mit meinem Kopfbuggy in B darüber nach, also schien es noch mehr Buggy zu sein. Sie können gierig (?) Solche Probleme von vorne zählen, aber es ist wichtig, ** genau zu erfassen, was passiert, nachdem jede Person gekommen ist **, und die Zeit zu dieser Zeit und die Zeit, um nach der Antwort zu fragen, sind Da sie unterschiedlich sind, bereiten Sie zwei Variablen vor. Fälle sollten danach klassifiziert werden, ob bei Ankunft einer bestimmten Person heißes Wasser verfügbar ist oder nicht.

answerC.py

t=0
N,T=map(int,input().split())
nt=[int(i) for i in input().split()]
ans=0
for i in range(N):
    if nt[i]>t:
        ans+=T
    else:
        ans+=(T-(t-nt[i]))
    t=nt[i]+T
print(ans)

D Problem

Ich hatte eine kurzfristige Vorstellung von einem einfachen Rucksack → DP-Chance. Ich bin zu verrückt Wenn Sie sich die Einschränkungen ansehen, kann das maximale Gewicht über $ 10 ^ 9 $ liegen, sodass DP es nicht rechtzeitig schaffen kann. Wenn Sie sich das Problem genau ansehen, können Sie sehen, dass ** n extrem klein ist ($ O (n ^ 3) $ kann es sich leisten) und dass es nur vier Möglichkeiten wiegt **. Mit anderen Worten, es sollten viele Artikel mit demselben Gewicht vorhanden sein, damit Sie sehen können, dass ** es besser ist, Artikel mit demselben Gewicht in absteigender Reihenfolge des Werts auszuwählen . Selbst wenn Sie darüber nachdenken, wie viele Gewichte Sie aus n <= 100 auswählen und die Vierfachschleife drehen sollen, sind es nur etwa 25 ^ 4 <10 ^ 6 $, sodass Sie es sich leisten können. ( Dieser Sinn für Berechnung ist wichtig **) ** Es ist jedoch notwendig, zuerst die kumulative Summe zu betrachten, damit die Summe der Dinge jedes Gewichts durch O (1) ** erhalten werden kann. (C ++ scheint pünktlich zu sein, ohne die kumulative Summe zu berücksichtigen.) Eine einfache Implementierung davon ist der Code für `answerD1.py```. Der Code war nicht lesbar, deshalb habe ich ihn in den Code answerD2.py``` umgeschrieben. (Die Vierfachschleife ist auch eine Dreifachschleife.) Obwohl es neu geschrieben wurde, gibt es noch Raum für Verbesserungen, so dass `` answerD3.py die Unterbrechung in der zweiten Hälfte der for-Schleife stark nutzt. Ich habe versucht, es hier zum schnellsten Code zu machen und habe es schließlich so etwas wie `` `answerD4.py gemacht (ich habe viel vom ersten Sortierteil usw. entwickelt), aber es sind nur bis zu 32 ms Kazu erreichte nicht die schnellste von 26ms. (Ich habe zwei Stunden gebraucht, um den Code zu verbessern. Es war schwer.)

answerD1.py

n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    if wv[i][0]==w0:
        k=wv[i][1]+x[0][-1]
        l=len(x[0])
        if l*w0<=w:x[0].append(k)
    elif wv[i][0]==w0+1:
        k=wv[i][1]+x[1][-1]
        l=len(x[1])
        if l*(w0+1)<=w:x[1].append(k)
    elif wv[i][0]==w0+2:
        k=wv[i][1]+x[2][-1]
        l=len(x[2])
        if l*(w0+2)<=w:x[2].append(k)
    else:
        k=wv[i][1]+x[3][-1]
        l=len(x[3])
        if l*(w0+3)<=w:x[3].append(k)
#print(x)
ma=0
for i in range(len(x[0])):
    for j in range(len(x[1])):
        for k in range(len(x[2])):
            for l in range(len(x[3])):
                ma_sub=0
                if i*w0+j*(w0+1)+k*(w0+2)+l*(w0+3)<=w:
                    ma_sub+=x[0][i]
                    ma_sub+=x[1][j]
                    ma_sub+=x[2][k]
                    ma_sub+=x[3][l]
                ma=max(ma,ma_sub)
print(ma)

answerD2.py

n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])#reverse
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
for i in range(l3):
    for j in range(l2):
        for k in range(l1):
            d=w-(i*(w0+3)+j*(w0+2)+k*(w0+1))
            if d>=0:
                ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,len(x[0])-1)]
            ma=max(ma,ma_sub)
print(ma)

answerD3.py

n,w=map(int,input().split())
wv=[tuple(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])#reverse
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
#print(x)
#print(w0)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)

answerD4.py

n,w=map(int,input().split())
w_sub,v_sub=map(int,input().split())
w0=w_sub
inf=1000000001
x=[[inf,v_sub],[inf],[inf],[inf]]
for i in range(n-1):
    w_sub,v_sub=map(int,input().split())
    z=w_sub-w0
    x[z].append(v_sub)
for i in range(4):
    x[i].sort(key=lambda x:-x)
    x[i][0]=0
    l_sub=len(x[i])
    for j in range(1,l_sub):
        x[i][j]+=x[i][j-1]

ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)