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

Benötigte Zeit

Impressionen

Ich konnte den Bachacon auf dem dritten Platz beenden, wahrscheinlich weil ich mich besser fühlte. Die letzte Frage war jedoch nicht bewiesen und ich habe sie etwas anders als die Antwort bestanden, daher möchte ich die Antwort genau prüfen.

Problem A

Hinauftragen. Ich habe math.ceil wegen des Fehlers nicht verwendet. Ich habe keine Lust, math.ceil für die Zukunft zu verwenden.

answerA.py

a,b=map(int,input().split())
print(-((-a-b)//2))

B-Problem

Denken Sie nur an die Größe des sortierten. Ich habe die Größe der Liste beiläufig verglichen, aber ** der Größenvergleich der Liste funktioniert genauso wie der Größenvergleich der Zeichenfolge **, nicht wahr?

answerB.py

s,t=sorted(list(input())),sorted(list(input()),reverse=True)
print("Yes" if s<t else "No")

C-Problem

Ich war auch überrascht, weil ich ein Problem mit der Groupby-Funktion hatte. Altes Problem Ist es nicht ein zu großes Problem, die Groupby-Funktion zu verwenden? ?? Teilen Sie sich nach Zahlen in Gruppen ein und entfernen Sie alle, wenn weniger als diese Zahl vorhanden sind. Wenn mehr als diese Zahl vorhanden ist, entfernen Sie sie, bis sie dieselbe Zahl haben.

answerC.py

n=int(input())
a=sorted(list(map(int,input().split())))

def groupby():
    global a
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

b=groupby()
ans=0
for i in b:
    if i[0]>i[1]:
        ans+=i[1]
    else:
        ans+=(i[1]-i[0])

print(ans)

D Problem

Überlegen Sie zunächst, ** welche Art von Verhalten der Roboter in F bzw. T zeigt **. Zuallererst ist F einfach. Wenn F für k Teile fortgesetzt wird, bewegt es sich um k Teile in die zu diesem Zeitpunkt gerichtete Richtung. Was ist im Gegenteil, wenn es k aufeinanderfolgende T gibt? Zu diesem Zeitpunkt ändert sich nicht, wie weit Sie gehen, aber die Richtung ändert sich. Beachten Sie, dass es nur vier Richtungen gibt. Wenn sich die Richtungen um 180 Grad unterscheiden, kann gesagt werden, dass sich das Positive und das Negative in derselben Richtung unterscheiden. Mit anderen Worten, ** am Ende stellt sich heraus, dass es nur zwei Richtungen gibt **, und wenn Sie eine kleine Figur zeichnen und darüber nachdenken, ** ändert sich die Richtung nicht, wenn k gerade ist, und die Richtung ändert sich, wenn k ungerade ist **. verstanden. Aus dem Obigen können wir sehen, wie weit sich jedes kontinuierliche F entweder in der x-Achse oder in der y-Achse bewegt. Da die Richtung der x-Achse und die Richtung der y-Achse unabhängig voneinander betrachtet werden können, werden wir ** betrachten, was mit der Richtung der x-Achse ** unten passiert. Das nächste, woran Sie denken sollten, ist, dass Sie, wenn der Roboter $ f_1, f_2,…, f_k $ k-mal in Richtung der x-Achse vorrückt, entscheiden, ob jedes positive oder negative ($ 2 ^ k $ Weg) gemacht werden soll, und einfach die Summe addieren. Die Frage ist, ob es x sein kann. Hier habe ich $ f_1, f_2,…, f_k $ in absteigender Reihenfolge sortiert und positiv oder negativ ausgewählt, damit das größte f so nahe wie möglich an x liegt. Dies wurde jedoch unbewiesen gemacht, daher müssen wir es auf nachweisbare Weise tun (ich weiß nicht, warum es so gemacht wurde). Hier mussten wir DP verwenden, wobei wir feststellten, dass es $ 2 ^ k $ war. Das heißt, von- (absoluter Wert von $ f_1, f_2,…, f_k $) bis zum absoluten Wert von $ f_1, f_2,…, f_k $ wählen Sie $ f_1, f_2,…, f_k $ in der Reihenfolge und DP Du musst es nur tun. Es kann gesagt werden, dass der Roboter die Koordinaten (x, y) erreichen kann, wenn er wie oben beschrieben auf x gesetzt werden kann und die y-Koordinate auch auf y gesetzt werden kann. Außerdem war der zweite Code der schnellste in PyPys Code.

answerD.py

from sys import exit
s=input()
x,y=map(int,input().split())

def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2
s=groupby(s)
a,b=[],[]
turn=True
#Wenn gerade am Anfang
if s[0][0]=="F":
    x-=s[0][1]
    s.pop(0)
for i in s:
    if i[0]=="F":
        if turn:
            a.append(i[1])
        else:
            b.append(i[1])
    else:
        if i[1]%2==1:
            turn=not turn
a.sort(reverse=True)
b.sort(reverse=True)
for i in a:
    if x>0:
        x-=i
    else:
        x+=i
for i in b:
    if y>0:
        y-=i
    else:
        y+=i
if x!=0 or y!=0:
    print("No")
else:
    print("Yes")

answerD_faster.py

def main():
    from sys import exit
    s=input()
    x,y=map(int,input().split())

    def groupby(a):
        a2=[[a[0],1]]
        for i in range(1,len(a)):
            if a2[-1][0]==a[i]:
                a2[-1][1]+=1
            else:
                a2.append([a[i],1])
        return a2

    s=groupby(s)
    a,b=[],[]
    turn=True
    #Wenn gerade am Anfang
    if s[0][0]=="F":
        x-=s[0][1]
        s.pop(0)
    for i in s:
        if i[0]=="F":
            if turn:
                a.append(-i[1])
            else:
                b.append(-i[1])
        elif i[1]%2==1:
            turn=not turn
    a.sort()
    b.sort()
    for i in a:
        x=abs(x)-abs(i)
    if x!=0:
        print("No")
        exit()
    for i in b:
        y=abs(y)-abs(i)
    if y!=0:
        print("No")
        exit()
    print("Yes")
main()