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

Frühere Fragen zum ersten Mal gelöst

Benötigte Zeit

Problem A

Ich fand es ärgerlich, Fälle danach zu klassifizieren, ob sie gleich waren, aber die Antwort war klüger.

answerA.py

x=[1,3,5,7,8,10,12]
y=[4,6,9,11]
z=[2]

a,b=map(int,input().split())

if (a in x and b in x) or (a in y and b in y) or (a in z and b in z):
    print("Yes")
else:
    print("No")

amswerA_better.py

xyz=[0,2,0,1,0,1,0,0,1,0,1,0]
a,b=map(int,input().split())
print("Yes" if xyz[a-1]==xyz[b-1] else "No")

B-Problem

Fügen Sie entsprechend "#" hinzu

answerB.py

h,w=map(int,input().split())
hw=["#"*(w+2)]
for i in range(h):
    hw.append("#"+input()+"#")
hw.append("#"*(w+2))
for i in range(h+2):
    print(hw[i])

C-Problem

Obwohl es ein C-Problem war, war es schwierig, aber die Schwierigkeit war hellblau. Als ich es nachgeschlagen habe, war es der zweitlangsamste der AC-Codes, aber ich persönlich mag diesen schlammigen Code. (Ich habe versucht, es zu schreiben, aber es war ein ziemlich schrecklicher Code. Ich bereue es.) Erstens, wenn es durch 3 teilbar war, gibt es 0 aus, aber dies ist nicht notwendig. In der else-Anweisung gibt es eine Methode, um ein horizontal langes Rechteck mit der ersten for-Anweisung zu erstellen und das verbleibende Rechteck so weit wie möglich in zwei gleiche Teile zu teilen. Es gibt also eine Methode, um es vertikal und horizontal zu teilen. Ich habe alle Bereiche des Rechtecks aufgeschrieben, die zu spüren scheinen. (Ich habe beim Überprüfen festgestellt, dass ** es viele Duplikate und viele nutzlose Verarbeitungen ** gibt.) Die zweite besteht darin, ein vertikal langes Rechteck zu erstellen und dieselbe Verarbeitung durchzuführen. Auch der zweite Code ist eine Verbesserung. Der Verbesserungsprozess ist so. (Ich lösche den roten Teil, weil ich ihn nicht brauche.) (Der untere Teil ist der erste Code.)

answerC.py

h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
else:
    x=[]
    for i in range(1,w):
        sub=[]
        sub.append([h*i,h*((w-i)//2),h*(w-i)-h*((w-i)//2)])
        sub.append([h*i,h*((w-i)//2+1),h*(w-i)-h*((w-i)//2+1)])
        sub.append([h*i,(w-i)*(h//2),h*(w-i)-(w-i)*(h//2)])
        sub.append([h*i,(w-i)*(h//2+1),h*(w-i)-(w-i)*(h//2+1)])
        for j in sub:
            x.append(max(j)-min(j))
    for i in range(1,h):
        sub=[]
        sub.append([w*i,w*((h-i)//2),w*(h-i)-w*((h-i)//2)])
        sub.append([w*i,w*((h-i)//2+1),w*(h-i)-w*((h-i)//2+1)])
        sub.append([w*i,(h-i)*(w//2),w*(h-i)-(h-i)*(w//2)])
        sub.append([w*i,(h-i)*(w//2+1),w*(h-i)-(h-i)*(w//2+1)])
        for j in sub:
            x.append(max(j)-min(j))
    print(min(x))

answerC_better.py

h,w=map(int,input().split())
x=[]
for i in range(1,w):
    x1=[h*i,h*((w-i)//2),h*(w-i)-h*((w-i)//2)]
    x2=[h*i,(w-i)*(h//2),h*(w-i)-(w-i)*(h//2)]
    x.append(min(max(x1)-min(x1),max(x2)-min(x2)))
for i in range(1,h):
    x1=[w*i,w*((h-i)//2),w*(h-i)-w*((h-i)//2)]
    x2=[w*i,(h-i)*(w//2),w*(h-i)-(h-i)*(w//2)]
    x.append(min(max(x1)-min(x1),max(x2)-min(x2)))
print(min(x))

D Problem

Die erste Hälfte N Elemente von a 'setzen sich aus den ersten 2N Elementen zusammen, und die zweite Hälfte N Elemente von a' setzen sich aus den letzten 2N Elementen zusammen. Wenn hier 2N Elemente als a ausgewählt werden und die N Elemente der ersten Hälfte und der zweiten Hälfte berücksichtigt werden, wird das letzte Element der ersten Hälfte als das k (N <= k <= 2N) -te Element des ursprünglichen a betrachtet. Wenn Sie dies tun, können Sie auch sehen, dass das k-te und frühere in der ersten Hälfte von a 'und das k-te und spätere in der zweiten Hälfte von a' enthalten sind. Um zu maximieren (die Summe der N Elemente der ersten Hälfte von a ') - (die Summe der N Elemente der zweiten Hälfte von a'), wird die Summe der N Elemente der ersten Hälfte von a'maximiert und die Summe der N Elemente der zweiten Hälfte von a'ist das Maximum. Da es nur notwendig ist, es zu minimieren, werden die ersten halben k Teile in absteigender Reihenfolge sortiert und die Summe von N Elementen wird von vorne betrachtet, und die zweite Hälfte von 3N-k Teilen wird in aufsteigender Reihenfolge sortiert und die Summe von N Elementen wird von vorne betrachtet. ist. Wenn Sie jedoch einfach k bewegen und darüber nachdenken, ist dies der Berechnungsbetrag von O (N * N * logN) und TLE. Also dachte ich darüber nach, was passieren würde, wenn ich k erhöhen würde. Wir haben eine Methode verwendet, um zu klassifizieren, ob das neu hinzugefügte Element beim Inkrementieren kleiner als das kleinste Element ist oder nicht. Wenn es klein ist, wird es nicht hinzugefügt, und wenn es groß ist, wird die Summe aktualisiert. Es war mühsam, etwas zu speichern und einzeln zu vergleichen (die Summe der N Elemente in der ersten Hälfte von a'wird hier betrachtet). Was ich mir hier hätte einfallen lassen sollen, ist die Verwendung von ** Priority_queue **. Wenn Sie später darüber nachdenken, gibt es viele offensichtliche Punkte. Dies liegt daran, dass Sie mit Priority_queue ** Elemente mit hoher Priorität in Protokollstunden abrufen und die Geschwindigkeit in Protokollstunden ** erhöhen können. Warum haben Sie sich nicht für Priority_queue entschieden, wenn Sie versuchen, Fälle mit dem kleinsten (oder maximalen) Wert als Grenze zu trennen? Bedauern. Nachdem ich eine Richtlinie erstellt hatte, konnte ich einen Pan ausführen. Priority_queue ist großartig. Ich habe Pythons Heapq nicht viel verwendet, weil ich oft die Priority_-Warteschlange von C ++ verwende, aber ich denke, es ist unpraktisch, weil ich die Priorität nicht wie C ++ ändern kann. Ich werde versuchen herauszufinden, was ich tun kann, wenn ich Lust dazu habe (ich möchte es nicht tun, weil es ein Ärger ist, wenn ich in der Klasse einen neuen machen muss).

answerD.py

import heapq

n=int(input())
a1=[]
b1=[]
a2=[]
b2=[]
s=input().split()
for i in range(3*n):
    if i<n:
        a1.append(int(s[i]))
    elif i>=2*n:
        b1.append(-int(s[i]))
    else:
        a2.append(int(s[i]))
        b2.append(-int(s[3*n-i-1]))
suma=[sum(a1)]
sumb=[sum(b1)]
heapq.heapify(a1)
heapq.heapify(b1)

for i in range(0,n):
    heapq.heappush(a1,a2[i])
    k=heapq.heappop(a1)
    l=suma[-1]
    suma.append(l+a2[i]-k)
for i in range(0,n):
    heapq.heappush(b1,b2[i])
    k=heapq.heappop(b1)
    l=sumb[-1]
    sumb.append(l+b2[i]-k)

ma=-1000000000000000
for i in range(n+1):
    ma=max(ma,suma[i]+sumb[-i-1])
print(ma)