[PYTHON] AtCoder Beginner Contest 160 Bewertung

Die Ergebnisse dieser Zeit

スクリーンショット 2020-03-28 22.48.46.png

Eindrücke dieser Zeit

Ich hätte stark sein sollen, aber ich war zum ersten Mal seit drei Wochen nervös beim Wettbewerb und konnte meine Fähigkeiten nicht unter Beweis stellen. Obwohl ich das C-Problem in insgesamt etwa 7 Minuten gelöst habe, konnte ich das D-Problem und darüber hinaus aufgrund eines Fehlers in meinem Kopf nicht lösen (ich habe das F-Problem nicht gesehen). Es ist wichtig, schnell wieder normal zu werden, aber zum Zeitpunkt eines wichtigen Tests wird es immer ein Whiteout sein, daher denke ich, dass ich mein Bestes im Wettbewerb geben muss, unter der Annahme, dass es ein Whiteout sein wird. (Wenn Sie weiß werden, würde ich es begrüßen, wenn Sie mir sagen könnten, was zu tun ist). Wenn Sie über überwältigende Fähigkeiten verfügen (blauer Kodierer oder höher), können Sie diese definitiv lösen. Ich denke, die einzige Abkürzung besteht darin, sich selbst zu widmen. Nachtrag: Unmittelbar nach dem Wettbewerb dachte ich, ich wäre kein lebenslanger Wettkampfprofi, aber der Wunsch, mich zu widmen, scheint sich durchzusetzen. Die Rate steigt nicht wie erwartet, aber ich möchte meine Bemühungen bis vor den Sommerferien fortsetzen.

Problem A

Das A-Problem ist beim ternären Operator schneller.

A.py


s=input()
print("Yes" if s[2]==s[3] and s[4]==s[5] else "No")

B-Problem

Da die Priorität in der Größenordnung von 500 → 5 höher ist, wird sie als solche berechnet.

B.py


x=int(input())
y=x//500
z=(x-y*500)//5
print(y*1000+z*5)

C-Problem

Sie können sehen, dass die kürzeste Entfernung darin besteht, jedes Haus nur einmal und alle Häuser zu durchlaufen. Angenommen, Sie folgen vom ersten Haus zum n-ten Haus, um zu sehen, dass der Abstand zwischen dem ersten Haus und dem n-ten Haus kürzer ist als um den See, der K Meter entfernt ist. Daher ist K meter- (der größte Abstand zwischen benachbarten Häusern) die Antwort, die Sie suchen.

C.py


k,n=map(int,input().split())
a=list(map(int,input().split()))
ma=0
for i in range(n-1):
    ma=max(ma,a[i+1]-a[i])
print(k-max(ma,a[0]+k-a[n-1]))

D Problem

Da $ n = 10 ^ 3 $ ist, habe ich nicht bemerkt, dass sogar $ O (n ^ 2) $ vergangen ist, also habe ich die Zeit geschmolzen. Ich bin zu verrückt Zuallererst ist ** das Schätzen des Berechnungsaufwands grundlegend , und ich habe Beispielfall 3 ausprobiert ( Das Experimentieren mit Stichproben ist ebenfalls grundlegend **), aber es hat nicht funktioniert, und ich habe es nach dem Wettbewerb bestätigt * * Es gab ein Muster **, das ich vergessen habe zu zählen ... Zuallererst ist das Merkmal dieses Problems, dass X und Y verbunden sind. Wenn Sie außerdem feststellen, dass XY nur einmal passiert, weil es die kürzeste Entfernung ist, können Sie denken, dass es besser ist, nach ** XY oder nicht ** zu klassifizieren, wenn (i, j) eingestellt ist. Ich werde. Wenn Sie dies tun können, können Sie es sofort in ein einfaches Problem verwandeln. Die kürzeste Entfernung, wenn Sie X-Y nicht passieren, ist j-i, und die kürzeste Entfernung, wenn Sie X-Y passieren, ist $ abs (X-i) + abs (j-Y) + 1 $ (1 ist die kürzeste Entfernung von X-Y). Versuchen Sie dies für alle (i, j) und es ist $ O (n ^ 2) $, und die Antwort besteht darin, aufzuzeichnen, welche der kürzesten Abstände 1 bis n-1 in einem separat vorbereiteten Array liegen. Du kannst Fragen.

Was ich am meisten über dieses Problem gelernt habe

Wenn auch die Probe nicht passt, schreiben Sie die Probe von Hand und prüfen Sie, ob Ihre Überlegung korrekt ist

nicht wahr.

answerD.py


n,x,y=map(int,input().split())
ans=[[1000000]*n for i in range(n)]
for i in range(n-1):
    for j in range(i+1,n):
        ans[i][j]=min(j-i,abs(x-1-i)+1+abs(y-1-j))
_ans=[0]*(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        _ans[ans[i][j]-1]+=1
for i in range(n-1):
    print(_ans[i])

E Problem

Ich konnte dieses Problem nicht lösen, weil ich mit dem D-Problem ungeduldig war, aber es war nicht schwierig. ** Die Problemstellung falsch zu verstehen ** war schrecklich und ich habe falsch verstanden, dass ** ich einen oder mehrere farblose Äpfel auswählen musste **. Außerdem war der Code ziemlich kompliziert, da ich rote und grüne Äpfel auswählte und gleichzeitig farblose Äpfel auswählte. Wenn Sie sie gleichzeitig auswählen, geht die Symmetrie verloren, je nachdem, welche der roten und grünen Äpfel Sie ** zuerst ** auswählen, und Sie können vergessen, sie zu zählen. Also, hier ** um die Symmetrie aufrechtzuerhalten **, x rote Äpfel und x x grüne Äpfel in der Reihenfolge von dem mit dem größten Geschmack ** unabhängig vom Geschmack farbloser Äpfel ** Wählen Sie (beachten Sie, dass die Auswahl von mehr als x und mehr als y nicht in den x + y-Kandidaten zum Essen enthalten ist). Danach können Sie überlegen, wie viele farblose Äpfel Sie auswählen sollen, und diese in absteigender Reihenfolge der Köstlichkeiten auswählen. Außerdem können ** die farblosen Äpfel sowohl gegen die x ausgewählten roten Äpfel als auch gegen die y grünen Äpfel ** ausgetauscht werden, sodass die roten Äpfel und die grünen Äpfel ** zusammen ** weniger lecker sind. Sie können sie in der richtigen Reihenfolge anordnen und durch die farblosen Äpfel in der Reihenfolge der kleinsten ersetzen (wenn die farblosen Äpfel weniger lecker sind, müssen Sie sie nicht ersetzen, damit der Gesamtgeschmack der Äpfel zu diesem Zeitpunkt maximiert wird). In dem Moment, als ich es sah, erinnerte ich mich an ein ähnliches Problem und verwendete Heapq, aber es schien, als könnte ich es ohne Heapq lösen, wenn ich eine richtige Richtlinie hätte ([Writer-Lösung](https: //img.atcoder]). .jp / abc160 / editorial.pdf)). Der erste ist der Code für die Lösung, die Heapq verwendet, und der zweite ist der Code für die Lösung, die Heapq nicht verwendet.

answerE.py


import heapq
x,y,a,b,c=map(int,input().split())
def _int(x):
    return -int(x)
p=list(map(_int,input().split()))
q=list(map(_int,input().split()))
r=list(map(_int,input().split()))
heapq.heapify(p)
heapq.heapify(q)
heapq.heapify(r)

ans=[]
heapq.heapify(ans)
for i in range(x):
    _p=heapq.heappop(p)
    heapq.heappush(ans,-_p)
for i in range(y):
    _q=heapq.heappop(q)
    heapq.heappush(ans,-_q)
#ans ist in aufsteigender Reihenfolge, r ist in absteigender Reihenfolge
for i in range(x+y):
    if len(r)==0:break
    _ans=heapq.heappop(ans)
    _r=-heapq.heappop(r)
    if _r>=_ans:
        heapq.heappush(ans,_r)
    else:
        heapq.heappush(ans,_ans)
        break
print(sum(ans))

answerE_better.py


x,y,a,b,c=map(int,input().split())

p=sorted(list(map(int,input().split())),reverse=True)[:x]
q=sorted(list(map(int,input().split())),reverse=True)[:y]
r=sorted(list(map(int,input().split())),reverse=True)

p.extend(q)
ans=sorted(p)

#ans ist in aufsteigender Reihenfolge, r ist in absteigender Reihenfolge
for i in range(x+y):
    if len(r)==i or r[i]<ans[i]:
        break
    else:
        ans[i]=r[i]
print(sum(ans))

F Problem

Ich kann F diesmal nicht lösen, weil der Schock, den D und E nicht lösen konnten, groß ist. Ich würde es gerne bei einer anderen Gelegenheit lösen.

Recommended Posts

AtCoder Beginner Contest 160 Bewertung
AtCoder Anfängerwettbewerb 178 Bewertung
AtCoder Anfängerwettbewerb 166 Bewertung
AtCoder Anfängerwettbewerb 167 Bewertung
AtCoder Beginner Contest 164 Bewertung
AtCoder Beginner Contest 169 Bewertung
AtCoder Beginner Contest 181 Bewertung
AtCoder Beginner Contest 171 Bewertung
AtCoder Beginner Contest 182 Bewertung
AtCoder Beginner Contest 180 Bewertung
AtCoder Anfängerwettbewerb 177 Rückblick
AtCoder Anfängerwettbewerb 168 Bewertung
AtCoder Beginner Contest 179 Bewertung
AtCoder Beginner Contest 172 Bewertung
AtCoder Anfängerwettbewerb 176 Bewertung
AtCoder Anfängerwettbewerb 175 Bewertung
AtCoder Anfängerwettbewerb 174 Bewertung
AtCoder Beginner Contest 153 Bewertung
AtCoder Anfängerwettbewerb 156 Bewertung
AtCoder Beginner Contest 161 Bewertung
AtCoder Beginner Contest 170 Bewertung
AtCoder Beginner Contest 165 Bewertung
AtCoder Beginner Contest 173 Bewertung
AtCoder Anfängerwettbewerb 155 Bewertung
AtCoder Beginner Contest 162 Bewertung
AtCoder Anfängerwettbewerb 179
AtCoder Anfängerwettbewerb 172
AtCoder Anfängerwettbewerb 180
AtCoder Anfängerwettbewerb 173
Atcoder Anfänger Wettbewerb 153
AtCoder Beginner Contest 066 Überprüfen Sie frühere Fragen
AtCoder Anfängerwettbewerb 181 Hinweis
AtCoder Grand Contest 041 Bewertung
AtCoder Regular Contest 105 Bewertung
AtCoder Anfängerwettbewerb 180 Hinweis
AtCoder Anfängerwettbewerb 182 Hinweis
AtCoder Grand Contest 048 Bewertung
AtCoder Anfängerwettbewerb 156 WriteUp
AtCoder Grand Contest 045 Bewertung
AtCoder Grand Contest 044 Bewertung
AtCoder Beginner Contest 167 Memorandum
AtCoder Anfängerwettbewerb 183 Hinweis
AtCoder Regular Contest 106 Bewertung
AtCoder Anfängerwettbewerb 184 Hinweis
AtCoder Grand Contest 046 Bewertung
AtCoder Regular Contest 104 Bewertung
AtCoder Beginner Contest 102 Rückblick auf frühere Fragen
AtCoder Beginner Contest 072 Rückblick auf frühere Fragen
AtCoder Beginner Contest 085 Rückblick auf frühere Fragen
AtCoder Beginner Contest 113 Rückblick auf frühere Fragen
AtCoder Beginner Contest 074 Rückblick auf frühere Fragen
AtCoder Beginner Contest 051 Rückblick auf frühere Fragen
AtCoder Beginner Contest 127 Rückblick auf frühere Fragen
AtCoder Beginner Contest 119 Rückblick auf frühere Fragen
AtCoder Beginner Contest 151 Rückblick auf frühere Fragen
AtCoder Beginner Contest 075 Rückblick auf frühere Fragen
AtCoder Beginner Contest 054 Rückblick auf frühere Fragen
AtCoder Beginner Contest 110 Rückblick auf frühere Fragen