[PYTHON] AtCoder Beginner Contest 173 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Dieses Mal habe ich es ohne Konzentration und ohne angemessene Überlegung gelöst, also habe ich den niedrigsten Rang aller Zeiten aktualisiert und 2020 die niedrigste Leistung erzielt. Ich denke, dass das E-Problem hätte gelöst werden können, wenn ich meinen Kopf richtig benutzt hätte, und ich habe das Gefühl, dass D auch nicht berücksichtigt wurde. (Weil meine Gedanken auf dem Weg zusammengebrochen sind ...) Aber um ehrlich zu sein, ich bin mir nicht sicher, was ich ändern soll, um die Rate zu erhöhen ... Ich denke, es bleibt vorerst keine andere Wahl, als verschiedene Probleme zu lösen und die typischen Muster in den Körper einziehen zu lassen ...

Problem A

Ich war ungeduldig, deshalb ist es mir peinlich, es von diesem Punkt an verrückt zu lösen.

A.py

n=int(input())
if n%1000==0:
    print(0)
else:
    print(1000-n%1000)

B-Problem

Es ist ein Problem, das ich nicht wirklich mag, weil Tippfehler wahrscheinlich auftreten. Ich denke jedoch, ich könnte es besser schreiben, deshalb bereue ich es.

B.py

n=int(input())
d={"AC":0,"WA":0,"TLE":0,"RE":0}
for i in range(n):
    d[input()]+=1
print("AC x "+str(d["AC"]))
print("WA x "+str(d["WA"]))
print("TLE x "+str(d["TLE"]))
print("RE x "+str(d["RE"]))

C-Problem

Dieses Mal wurde aufgrund des C-Problems eine vollständige Bit-Suche durchgeführt. Ich möchte darüber nachdenken, wie die Zeilen und Spalten ausgewählt werden sollen, die in Rot gezeichnet werden sollen. Daher kopiere ich die zuerst eingegebene Matrix, überschreibe sie mit Rot (x) und zähle schließlich die Anzahl der verbleibenden Schwarz (#). Als ich diesen Kommentar schrieb, bemerkte ich, dass es einfach zu implementieren ist, wenn Sie sich nicht die Mühe machen, die angegebenen Zeilen und Spalten zu kopieren und zu zählen. Ich war seit dem ersten Grundproblem verrückt. vielleicht.

C.py

h,w,K=map(int,input().split())
c=[input() for i in range(h)]
ans=0
for i in range(2**h):
    for j in range(2**w):
        d=[[c[z][v] for v in range(w)]for z in range(h)]
        for k in range(h):
            if (i>>k)&1:
                for l in range(w):
                    d[k][l]="x"
        for k in range(w):
            if (j>>k)&1:
                for l in range(h):
                    d[l][k]="x"
        cnt=0
        for k in range(h):
            for l in range(w):
                cnt+=(d[k][l]=="#")
        ans+=(cnt==K)
print(ans)

D Problem

Ausführliche Informationen finden Sie unter Erläuterung. Hier finden Sie eine sinnliche Erklärung.

Zunächst scheint es besser zu sein, in der Reihenfolge der Person mit der höchsten Freundlichkeit anzukommen **, da sich die Situation nicht verbessert, selbst wenn die Person mit der niedrigsten Freundlichkeit zuerst ankommt.

Unter dieser Annahme können Sie auch an die ** Gier-Methode ** denken, die die größte Position ist, die Sie im Moment unterbrechen sollten. Das heißt, Sie können wie folgt unterbrechen:

In der obigen Abbildung steht die Freundlichkeit der Person auf der linken Seite und der Komfort auf der rechten Seite. Sie können sehen, dass $ A_i $ die Freundlichkeit von $ A_ {[\ frac {i + 1} {2}]} $ erhält, wenn Sie so unterbrechen (stellen Sie sich das als vollständige Dichotomie vor). Überlegen.). Wenn Sie dies bisher bemerken, ist die Implementierung einfach und sieht wie folgt aus.

Ich dachte, ich wäre nicht gierig ** und warf es weg, aber ich möchte bedenken, dass die Grundlagen gierig sind.

D.py

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=0
for i in range(1,n):
    ans+=a[i//2]
print(ans)

E Problem

Die Grundidee ist nicht schwierig, aber es gibt so viele Eckfälle, dass es ein ernstes Problem bei der Montage war.

Ich konnte nicht an der Implementierung arbeiten, weil ich dachte, es wäre einfacher für mich, darüber nachzudenken, aber als ich die Antwort sah, hatte ich das Gefühl, dass mir immer noch die Fähigkeiten fehlten, weil sie ordentlich geschrieben waren. ** Ich möchte die Fähigkeit erlangen, über Fälle fest nachzudenken **.

Betrachten Sie zunächst den Fall, in dem das Produkt aus ** $ K $ -Zahlen eine negative Zahl ist, und beachten Sie, dass es nur wenige Muster gibt, die negativ sind **. Dann ist das Produkt von ** $ K $ -Nummern negativ, wenn nur eine ungerade Anzahl von $ K $ -Nummern ausgewählt werden kann **. Wenn hier eine oder mehrere Zahlen größer oder gleich 0 sind, können Sie die Gerade / Ungerade der Anzahl der in der $ K $ -Nummer enthaltenen negativen Zahlen steuern, je nachdem, ob die Zahl enthalten ist oder nicht. Daher ist das Produkt von $ K $ -Zahlen negativ, wenn alle gegebenen $ N $ -Zahlen negativ sind und $ K $ ungerade (①) ist und $ N = K $ und gegeben ist. Wenn die Anzahl von $ N $ eine ungerade Anzahl von negativen Zahlen (②) enthält, ist dies entweder der Fall.

Berücksichtigung von ① ↓ Es ist nicht schwer zu berechnen, wenn die angegebene Anzahl von $ N $ alle negativ ist oder alle 0 oder mehr sind, also habe ich versucht, sie alle zusammen zu berechnen. Das heißt, wenn die angegebene Anzahl von $ N $ alle negativ ist, wenn $ K $ gerade ist, ist das Produkt positiv, so dass das Produkt von $ K $ das größte in der Reihenfolge von dem mit dem größten absoluten Wert und $ ist Wenn K $ ungerade ist, ist das Produkt negativ, so dass das Produkt von $ K $ in aufsteigender Reihenfolge des absoluten Wertes das größte ist. Wenn alle Zahlen 0 oder mehr sind, ist das Produkt von $ K $ das Maximum in der Reihenfolge von dem mit dem größten absoluten Wert.

Implementierung von ① ↓ Speichern Sie Zahlen größer oder gleich 0 in "ap", speichern Sie negative Zahlen in "am" und $ N $, wenn "len (ap) == 0" oder "len (am) == 0" Sind alle negativen Zahlen (oder alle positiven Zahlen), so implementieren Sie wie berücksichtigt. Außerdem sollten "ap" und "am" in absteigender Reihenfolge der absoluten Werte sortiert werden.

Berücksichtigung und Umsetzung von ② ↓ Wenn $ N = K $, betrachten Sie das Produkt der angegebenen $ N $ -Zahlen. Dies wird sofort nach Erhalt der Eingabe angefordert.

Auf der Grundlage der obigen Ausführungen betrachten wir die Richtlinie unter **, bei der der maximale Wert des Produkts aus $ K $ -Nummern garantiert 0 oder mehr ** beträgt. (Ich war aus diesem Bereich verwirrt, weil ich über die Politik verwirrt war.)

Erstens ist das Produkt von $ K $ nicht 0 oder mehr, es sei denn, ** negative Zahlen sind gerade **, daher wird das Produkt durch Paarung ** in der Reihenfolge der Zahl mit dem größten absoluten Wert berechnet. Um eine negative Zahl und eine Zahl größer oder gleich 0 auszuwählen, wird das Produkt berechnet, indem die Zahl größer oder gleich 0 in absteigender Reihenfolge gepaart wird, und diese werden in absteigender Reihenfolge in "apm2" gespeichert. (Danach möchte ich überprüfen, wie viele Zahlen 0 oder mehr ausgewählt sind. Markieren Sie also 1 für Zahlen 0 oder mehr und 0 für negative Zahlen.)

Hier besteht beim Pairing die Möglichkeit, dass eine negative Zahl und eine Zahl größer oder gleich 0 übrig bleiben. Wenn Sie jedoch eine negative Zahl auswählen, müssen Sie diese nicht auswählen, da das Produkt negativ ist. Wählen Sie daher eine positive Zahl. Bitte beachten Sie, dass eine Möglichkeit besteht.

Erstens, wenn ** $ K $ gerade ist **, können Sie das Produkt von $ [\ frac {k} {2}] $ Zahlen vor apm2 finden, aber ** $ K $ ist Für ungerade Zahlen ** müssen Sie zusätzlich zur Zahl $ [\ frac {k} {2}] $ eine andere Zahl auswählen. Wenn Sie zu diesem Zeitpunkt "Wählen Sie eine der größten positiven Zahlen aus, die noch nicht ausgewählt wurden (✳︎1)" auswählen, ist dies in den folgenden Fällen nicht optimal.

5 3
-5 -1 1 2 3

Im obigen Fall ist -5, -1,3 das Beste, aber gemäß (✳︎1) ist 1,2,3 das Beste. Mit anderen Worten kann es optimal sein, "das größte ausgewählte Paar positiver Zahlen auszuwählen, mit Ausnahme der kleinsten Zahl, die nicht durch" apm2 "(✳︎2) ausgewählt wird". (** Überprüfen Sie unbedingt die Optimalität mit der gierigen Methode! **)

Während Sie also den Index in ap der Zahl aufzeichnen, die als nächstes als positive Zahl in p ausgewählt werden soll, ans zuerst die Nummer von $ [\ frac {k} {2}] $ von vorne. Ich werde anhängen` (** Da der zu entfernende Vorgang mühsam ist, habe ich versucht, ihn einmal im Array zu speichern, ohne nach dem Produkt zu fragen **).

Wenn $ K $ gerade ist, wird das Produkt aller Zahlen von ans berechnet, und wenn $ K $ ungerade ist, gemäß (✳︎1) und (✳︎2) oben,ap [ Sie sollten entweder bei der Auswahl von p](①) oder bei der Auswahl von apm2 [k // 2] [0] ohneap [p-1](②) berücksichtigen.

Wenn hier "p == len (p)" ist, werden alle Zahlen über 0 aufgebraucht, so dass die Zahl, die p entspricht, nicht existiert und das Muster ① nicht existiert. Wenn "p == 0" ist, wurde noch kein Zahlenpaar größer oder gleich 0 verwendet, so dass Muster (2) nicht existiert. (** Vergiss nicht, Ausnahmen zu berücksichtigen! **)

Eine sorgfältige Umsetzung der oben genannten Punkte würde zu folgenden Ergebnissen führen: Wir haben auch eine Funktion ("Multarray") definiert, um das Produkt eines bestimmten Arrays geteilt durch $ 10 ^ 9 + 7 $ zu finden, um die Implementierung zu vereinfachen.

E.py

#x:Array
mod=10**9+7
def multarray(x):
    ret=1
    for i in x:
        ret*=i
        ret%=mod
    return ret

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

#n==Im Falle von k einfach anrufen
if n==k:
    print(multarray(a))
    exit()

#Wird separat für Zahlen größer oder gleich 0 und negative Zahlen gespeichert
ap,am=[],[]
for i in range(n):
    if a[i]>=0:
        ap.append(a[i])
    else:
        am.append(a[i])
#Nach Absolutwert sortieren
ap.sort(reverse=True)
am.sort()

#Wenn es nur Zahlen größer oder gleich 0 oder nur positive Zahlen gibt, werden die Fälle zuerst geteilt.
if len(am)==0:
    print(multarray(ap[:k]))
    exit()
if len(ap)==0:
    if k%2==0:
        print(multarray(am[:k]))
    else:
        print(multarray(am[::-1][:k]))
    exit()

#Paarweise lagern(Notieren Sie, ob es 0 oder mehr oder negativ ist)
apm2=[]
for i in range(len(am)//2):
    apm2.append((am[2*i]*am[2*i+1],0))
for i in range(len(ap)//2):
    apm2.append((ap[2*i]*ap[2*i+1],1))
apm2.sort(reverse=True)

#Überprüfen Sie, wo Sie als Nächstes mit einer Zahl größer oder gleich 0 suchen müssen
p=0
ans=[]
for i in range(k//2):
    p+=(2*apm2[i][1])
    ans.append(apm2[i][0])

#Wenn K gerade ist
if k%2==0:
    print(multarray(ans))
    exit()

ans_cand=[]
#Beim Hinzufügen eines
if p!=len(ap):
    ans_cand.append(multarray(ans)*ap[p]%mod)
#Beim Reduzieren von eins und Erhöhen von zwei
if p!=0:
    #Index verringern
    check_i=ans.index(ap[p-1]*ap[p-2])
    #ap[p-1]Bedienung zu reduzieren(Vermeiden Sie 0 Division)
    ans[check_i]=ap[p-2]
    ans.append(apm2[k//2][0])
    ans_cand.append(multarray(ans))
print(max(ans_cand))

F Problem

Ich habe es noch nicht gelöst. Ich werde bald einen Kommentar veröffentlichen.