[PYTHON] AtCoder Grand Contest 041 Bewertung
Ich möchte die AGC041 überprüfen, die ich neulich hatte.
Die Ergebnisse dieser Zeit
Ich denke, ich kann meine Punktzahl verbessern, weil ich sie zum ersten Mal abschließen konnte, aber ich musste meine Meinung über das C-Problem nur ein wenig ändern, deshalb wollte ich sie dreimal abschließen.
Problem A
Ich habe relativ schnell eine Lösung gefunden, aber ich habe 2WA ausgespuckt, weil ich schnell eine Lösung eingereicht habe, die eindeutig falsch war, und Python-Code als C ++ - Code eingereicht habe. Erstens ist es am einfachsten zu verstehen, wenn der Abstand zwischen Tabelle A und Tabelle B gerade ist. In diesem Fall sollten die Tischtennisspieler an jedem Tisch den Abstand zwischen den Tischen um 2 verringern und den Abstand geteilt durch 2 ausgeben. Als nächstes müssen wir den Fall betrachten, in dem der Abstand zwischen Tabelle A und Tabelle B ungerade ist. In diesem Fall können Sie den Abstand zwischen den beiden Tischen auch dann einstellen, indem Sie bis zum Ende (Tabelle 1 oder Tabelle N) gehen und dort in einer Runde bleiben. Zu diesem Zeitpunkt ist es notwendig, diejenige näher am Ende zu betrachten, so dass es ausreicht, die min-Seite mit c und d im folgenden Code auszugeben. (Wenn Sie die Formel hier richtig codieren, wird sie zu WA.) Der Schlüssel zu diesem Problem ist ** die Klassifizierung des Zustands während des Übergangs **. In diesem Problem können Sie sehen, dass Sie nur ** ** nicht zu einem anderen Tisch wechseln können, wenn Sie an Tabelle 1 gewinnen und wenn Sie an Tabelle N verlieren. Es ist auch leicht zu berücksichtigen, dass die Fälle, in denen beide nahe beieinander liegen, deutlich minimiert sind. In diesem Fall ist der Abstand gleichmäßig, und wenn sie sich am Rand befinden, ändert sich die Gleichmäßigkeit.
answerA.py
x=[]
n,a,b=map(int,input().split())
if (b-a)%2==0:
print((b-a)//2)
else:
c=(a-1)+(b-a+1)//2
d=(n-b)+(b-a+1)//2
print(min(c,d))
B-Problem
Ordnen Sie die Personen vorerst in absteigender Reihenfolge an. Zu diesem Zeitpunkt können die Fragen A1 bis Ap bedingungslos angenommen werden, da Frage P im Wettbewerb angenommen wird. Wenn Sie hier die Frage von Ap ändern können, die die niedrigste Punktzahl unter den P-Fragen aufweist, und eine kleinere Frage auswählen können, kann die Frage in den Wettbewerb übernommen werden. Wenn v <= p, stimmen Sie weiterhin für A1 ~ Ap-1 und Aj (j> = p + 1) und wissen Sie, dass Aj Ap überschreiten kann. Andererseits gibt es im Fall von v> p immer noch mehr Stimmen für Aj (j> = p + 1), selbst wenn alle Richter für A1 ~ Ap-1, Aj und ** Aj stimmen, die Ap überschreiten. Sie können sehen, dass es nicht möglich ist, nur mit ** zu urteilen (denn wenn es in Ap eine Abstimmung gibt, kann diese Aj überschreiten). Wenn wir nun überlegen, wie wir die verbleibenden Stimmen für den Richter auswählen sollen, müssen wir auch beachten, dass wir Aj überschreiten werden, selbst wenn wir für Ak (k> j + 1) stimmen. Mit anderen Worten, selbst wenn Sie für A1 ~ Ap-1 und Aj ~ An stimmen (zu diesem Zeitpunkt beträgt die Punktzahl der gestimmten Frage + m) und die verbleibenden Stimmen des Richters in Ap ~ Aj-1 eingeben, wird Aj dies tun Es kann gesagt werden, dass Aj in den Wettbewerb aufgenommen werden kann, wenn es Al (p <= l <= j-1) oder mehr für ein l ist. Sie können auch sehen, dass Ap ~ Aj-1 gleich Aj ist, wenn die verbleibenden Stimmen des Richters ** maximal gewählt werden, so dass Ap Aj nicht überschreitet (zu diesem Zeitpunkt ist Ap ~ Aj-1 das Original Da es größer als Aj ist, ist garantiert, dass die maximale Anzahl von Stimmen für jedes m nicht überschreitet.) Außerdem sind sie in absteigender Reihenfolge angeordnet, und ** Sie können nach einem bestimmten Aj nicht mehr am Wettbewerb teilnehmen, sodass Sie nach Dichotomie nach einem solchen Aj suchen können **. Um das Innere der Adoptionsfunktion zu erklären, müssen zunächst A1 bis Ap-1 nicht berücksichtigt werden, daher werden sie als [p-1:] geschnitten. b ist der Wert, wenn maximal für Ax + p + 1 gestimmt wird (x wird als 0-Index betrachtet). Wenn b nicht mehr als Ap ist, kann es nicht übernommen werden, daher wird False zurückgegeben (1), al gilt für alle Richter Bei der Gesamtzahl der Stimmen (jedoch wird A1 ~ Ap-1, Axe + p + 1 ~ An abstimmen, daher habe ich diesen Betrag bereits abgezogen) sind alle Stimmen der Richter aufgebraucht, wenn al 0 oder weniger ist Daher wird True zurückgegeben (2), s ist die Anzahl der Stimmen, die erforderlich sind, um Ap ~ Ax + p Ax + p + 1 (b) zu machen. Wenn al s überschreitet, False, andernfalls True. Zurückgeben.
answerB.py
n,m,v,p=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort(reverse=True)
a=a[p-1:]
le=len(a)
l,r=0,le-1
def adopt(x):
global a,n,m,v,p
b=a[x]+m
#(1)
if b<a[0]:
return False
al=v*m
al-=(n-x)*m
#(2)
if al<=0:
return True
s=x*b-sum(a[:x])
#(3)
if al>s:
return False
else:
return True
while l+1<r:
k=(l+r)//2
if adopt(k):
l=k
else:
r=k
if adopt(r):
print(p+r)
else:
print(p+l)
Code, den ich nach dem Wettbewerb sowohl am kürzesten als auch am schnellsten anstrebte ↓ (Es wurde ein halbfertiger Code, der weder sehr kurz noch früh war.)
answerB_better.py
n,m,v,p=map(int,input().split())
a=sorted(list(map(int, input().split())),reverse=True)[p-1:]
l,r=0,n-p
while l+1<r:
k=(l+r)//2
b=a[k]+m
if b<a[0] or (v-(n-k))*m>(k*b-sum(a[:k])): r=k
else: l=k
b=a[r]+m
print(p+l if(b<a[0] or (v-(n-r))*m>(r*b-sum(a[:r]))) else p+r)
C-Problem
Ich konnte es während des Wettbewerbs nicht lösen. Entsprechend der Überlegung während des Wettbewerbs ist es notwendig, die Anzahl der vertikal und horizontal platzierten Dominosteine auszugleichen. Wenn sie ausgeglichen werden, kann die Qualität auf 3 gesetzt werden, um eine Anordnung von Dominosteinen zu erstellen, die die Bedingungen erfüllen. Es stellt sich heraus (außer wenn n = 2,3). Wenn hier die Dominosteine unter Berücksichtigung der Symmetrie angeordnet wurden und n ein Vielfaches von 3 war, konnten wir die Anordnung der Dominosteine der Qualität 1 finden, indem wir die Dominosteine vertikal und horizontal in der Reihenfolge entlang der diagonalen Linie anordneten. Ich konnte jedoch keine hochsymmetrische Anordnung finden, wenn n kein Vielfaches von 3 war (** Ich sollte hier eine andere Methode in Betracht ziehen **). ** Große Zahlen funktionieren oft gut, wenn sie geteilt werden **. Denken Sie also auch an dieses Problem. Wenn man sich auf die partielle quadratische Matrix von der i-ten Reihe bis zur j-ten Reihe und der i-ten bis j-ten Spalte konzentriert, ist der Teil von der i-ten Reihe bis zur j-ten Reihe und der i-ten bis j-ten Spalte außer dieser quadratischen Matrix 0. Wenn ja, können Sie sehen, dass die Qualität der partiellen quadratischen Matrix von Zeile i zu Spalte j und von Spalte i zu Spalte j reicht. Daher wissen wir, dass wir eine solche partielle quadratische Matrix konstruieren sollten. In Anbetracht der Matrix, deren Qualität 3 oben ist, habe ich das Gefühl, dass sie in einer quadratischen Matrix 4. Ordnung oder höher zu finden scheint. Von hier aus werde ich mein Bestes geben, um eine solche quadratische Matrix zu finden. Bei Betrachtung der Methode von Antwort fand ich eine quadratische Matrix der Ordnung 3,4,5,6,7 und teilte die Fälle mit mod4, um sie quadratisch zu machen. Sie können quadratische Matrizen in der Reihenfolge auf der Diagonale der Matrix anordnen. (Von oben gezählt, ist es 4., 4., 4., ..., (4or5or6or7) Es ist wie folgt ausgerichtet.) Ich benutze mod6, um Fälle zu klassifizieren, in denen n ein Vielfaches von 3 ist, weil es eine einfache Anordnung gibt. Die Lösungsmethode ist jedoch wahrscheinlich die einfachste Methode, da eine quadratische Matrix der Ordnung 3,4,5,6,7,8 gefunden werden muss.
answerC.py
n=int(input())
if n==2:
print(-1)
else:
x=[]
if n%3==0:
for i in range(n//3):
x.append("."*(3*i)+"a"+"."*(n-3*i-1))
x.append("."*(3*i)+"a"+"."*(n-3*i-1))
x.append("."*(3*i)+".aa"+"."*(n-3*i-3))
elif n%6==1:
for i in range(n//6-1):
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+"ddg.ll"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.g.kk"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.hhj."+"."*(n-6*i-6))
x.append("."*(6*i)+"ffiij."+"."*(n-6*i-6))
x.append("."*(n-7)+".aab.c.")
x.append("."*(n-7)+"d..b.c.")
x.append("."*(n-7)+"d..eeff")
x.append("."*(n-7)+"g..mm.l")
x.append("."*(n-7)+"gnn...l")
x.append("."*(n-7)+"h...kkj")
x.append("."*(n-7)+"hii...j")
elif n%6==2:
for i in range(n//6-1):
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+"ddg.ll"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.g.kk"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.hhj."+"."*(n-6*i-6))
x.append("."*(6*i)+"ffiij."+"."*(n-6*i-6))
x.append("."*(n-8)+".a.bb.cc")
x.append("."*(n-8)+".a...m.j")
x.append("."*(n-8)+"..pp.m.j")
x.append("."*(n-8)+"hh..i.o.")
x.append("."*(n-8)+"gg..i.o.")
x.append("."*(n-8)+"..n.ll.k")
x.append("."*(n-8)+"f.n....k")
x.append("."*(n-8)+"f.dd.ee.")
elif n%6==4:
for i in range(n//6):
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+"ddg.ll"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.g.kk"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.hhj."+"."*(n-6*i-6))
x.append("."*(6*i)+"ffiij."+"."*(n-6*i-6))
x.append("."*(n-4)+"aacb")
x.append("."*(n-4)+"ffcb")
x.append("."*(n-4)+"hgdd")
x.append("."*(n-4)+"hgee")
else:
for i in range(n//6):
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+"ddg.ll"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.g.kk"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.hhj."+"."*(n-6*i-6))
x.append("."*(6*i)+"ffiij."+"."*(n-6*i-6))
x.append("."*(n-5)+"aabbc")
x.append("."*(n-5)+"g.h.c")
x.append("."*(n-5)+"gjh..")
x.append("."*(n-5)+"dj.ii")
x.append("."*(n-5)+"deeff")
for i in range(n):
print("".join(x[i]))
Nach D Problem
Ich hatte das Gefühl, dass es immer noch auf einem Niveau ist, das gelöst werden sollte, also würde ich es gerne herausfordern, wenn ich es das nächste Mal mache.
Recommended Posts