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

Benötigte Zeit

Impressionen

Ich konnte die WA für das D-Problem nicht bekommen, also musste ich ungefähr zwei Stunden nach dem Wettbewerb verbringen, um die WA zu bekommen. Außerdem war die Idee richtig und nur eine Zeile war falsch. Es war schmerzhaft. Außerdem war es ein dummer Fehler, deshalb würde ich gerne darüber nachdenken und es beim nächsten Mal nutzen.

Problem A

Teilen Sie das Produkt der Seiten, die den rechten Winkel einschließen, durch 2.

answerA.py

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

B-Problem

Mit anderen Worten, Sie können den Index ausgeben, wenn er zum zweiten Mal herauskommt. Verwalten Sie also die Zahlen mit set und geben Sie den Index aus, wenn die bereits eingestellten Zahlen herauskommen und brechen. Das ist gut.

answerB.py

x=set()
s=int(input())
ans=0
while True:
    ans+=1
    if s in x:
        print(ans)
        break
    x.add(s)
    
    if s%2==0:
        s=s//2
    else:
        s=3*s+1

C-Problem

Persönlich war es wirklich schwierig. Anstatt zu gießen, um die Höhe der Blumen zu erhöhen, dachte ich daran, sie von der endgültigen Höhe der Blumen abzusenken, um alle Höhen der Blumen auf 0 zu bringen. Zu diesem Zeitpunkt wird auch die Mindestanzahl für den Teil ausgewählt, bei dem andere Zahlen als ** fortlaufend sind, und die Nummer des ausgewählten Teils wird um diese Zahl reduziert. ** Der Vorgang wird wiederholt, sodass die anderen Zahlen als 0 fortlaufend sind. Es ist notwendig, den Index des linken Endes abzurufen und das rechte Ende des Teils ((1) und (2) entsprechen ihm). Da die Operation zum Auswählen der Mindestanzahl in (2) gleichzeitig ausgeführt wird, wird die Höhe um die Mindestanzahl in (3) verringert. Sie können das Problem lösen, indem Sie zusammenfassen, um wie viel Sie die Höhe aller Blumen gesenkt haben, bis Sie die Höhe aller Blumen auf 0 reduziert haben.

answerC.py

n=int(input())
h=list(map(int,input().split()))
ans=0
while True:
    l,m=-1,-1
    #(1)
    for i in range(n):
        if h[i]!=0:
            l=i
            break
    if l==-1:
        break
    if l==n-1:
        ans+=h[l]
        break
    r=l
    #(2)
    for i in range(l,n):
        if h[i]==0:
            break
        else:
            r=i
            if m==-1:
                m=h[i]
            else:
                m=min(m,h[i])
    #(3)
    for i in range(l,r+1):
        h[i]-=m
    ans+=m
print(ans)

D Problem

Zuerst habe ich versucht, die Art des Materials zu korrigieren **, aber ich dachte nicht, dass es eine effektive Möglichkeit gibt, die Art zu bestimmen, deshalb habe ich es sofort abgelehnt. Wenn Sie hier die gleiche Art von Material essen möchten, dachte ich, dass es besser ist, das mit den höchsten Grundgeschmackspunkten zu wählen. Ordnen Sie also zuerst ** in absteigender Reihenfolge der Grundköstlichkeitspunkte an und wählen Sie das K-te Material aus ** Ich dachte. Hier ist es notwendig, die Typen zu erhöhen und die Typbonuspunkte zu erhöhen, um die Zufriedenheitspunkte zu erhöhen, während das Material mit einem niedrigeren Grundpunkt der Köstlichkeit als das K-Material ausgewählt wird. Außerdem ist das Material, das den Typbonus erhöht, ** das mit den höchsten Grundpunkten der Köstlichkeit unter den Materialtypen, die noch nie zuvor gesehen wurden **. Darüber hinaus dürfen für das Material, das bei der Auswahl eines Materials ausgeschlossen wird, das den Typbonus erhöht, ** die Typbonuspunkte nicht gesenkt werden **, also ** die köstlichsten Grundpunkte des Materialtyps mit zwei oder mehr Materialtypen Ist niedrig **. Da es notwendig ist, aufzuzeichnen, wie viele Arten von Material bisher aufgenommen wurden, wird es in einem Wörterbuch namens kl gespeichert. Daher wäre es gut, diese gehorsam umzusetzen, aber die Umsetzung war ein wenig mühsam. Daher ** habe ich vergessen, die Variable now auf -1 zu setzen, um das nächste Material nach dem Entfernen des Materials zu scannen **, und die Überprüfung dauerte ungefähr zwei Stunden. Ich habe diese Überprüfung auch nach dem Bachacon durchgeführt, aber sie war langsam, da ** jetzt nicht gespeichert wurde und alle Indizes von 0 bis k-1 jedes Mal während des Bachacons gescannt wurden **. Ich möchte sicherstellen, dass das Programm verbessert wird, sobald ich der Meinung bin, dass der Rechenaufwand verdächtig ist. Außerdem dachte ich, dass der Code schwer zu lesen sein würde, wenn andere ihn lesen, deshalb habe ich im Kommentar viele Notizen hinterlassen. Bitte beachten Sie auch den Kommentar aus dem Code.

answerD.py

n,k=map(int,input().split())
#td ist in der Reihenfolge der Größe angeordnet
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

#Das Folgende ist ein Code, um den Zufriedenheitspunkt zu finden, wenn Sie den Punkt mit dem höchsten Grundpunkt der Köstlichkeit bis zum k-ten auswählen
ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans

#Unten finden Sie den Code für die Auswahl des Materials zur Erhöhung der Typbonuspunkte
now=k-1 #Das Material, das ausgeschlossen werden kann, ist 0~Bisher nach Index suchen
for i in range(k,n): #Das Material, das die Typbonuspunkte erhöht, ist k~n-Suche in der Reihenfolge nach Index bis 1
    if td[i][0] not in kl: #Bei bisher nicht ausgewähltem Material
        while now>=0: #Gibt es Material, das entfernt werden kann?(now<Wenn es 0 ist, ist das Scannen beendet und endet.)
            if kl[td[now][0]]>1: #Es können nur Materialtypen ausgeschlossen werden, die mehr als ein Material enthalten
                mi=td[now] #Notieren Sie sich die Arten des auszuschließenden Materials und die grundlegenden Punkte der Köstlichkeit
                kl[mi[0]]-=1 #Reduzieren Sie die Anzahl dieser Art von Material um eins
                now-=1 #Scannen Sie vom nächsten entfernten Material
                break
            now-=1 #Wenn nur ein Material vorhanden ist, scannen Sie das nächste
        if now==-1: #Wenn Sie mit dem Scannen fertig sind
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1] #Beachten Sie die Zufriedenheitspunkte, wenn Sie die Typbonuspunkte erhöhen(aktualisieren)
            kl[td[i][0]]=1 #Notieren Sie die Art des Materials
            ans_=max(ans,ans_)#Aktualisieren Sie, wenn die Zufriedenheitspunkte überschritten werden
            l+=1 #Erhöhen Sie die Art des Materials um eins(Ich dachte, es wäre zu spät, um es mit len zu bekommen)
print(ans_)