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

Benötigte Zeit

Impressionen

Ich hatte es satt, Probleme von 50 bis 70 zu machen, also habe ich eine ganz andere Nummer ausprobiert.

Problem A

Mit anderen Worten, drücken Sie immer die größere

answerA.py

a,b=map(int,input().split())
if a==b:
    print(2*a)
else:
    print(2*max(a,b)-1)

B-Problem

Stellen Sie sicher, dass Sie es tatsächlich von jedem Gasthaus aus sehen können. Fälle sollten danach klassifiziert werden, ob es ein Gasthaus gibt, das größer als dieses Gasthaus auf der Seeseite ist oder nicht.

answerB.py

n=int(input())
h=list(map(int,input().split()))
c=0
for i in range(n):
    for j in range(i):
        if h[j]>h[i]:
            break
    else:
        c+=1
print(c)

C-Problem

Es ist gut, bei solchen Problemen des Neulackiersystems auf den Endzustand zu achten. Da es nur entweder 010101 ... oder 101010 ... geben kann, versuchen Sie beide und lösen Sie die mit einer kleinen Anzahl von Umschreibungen.

answerC.py

s=input()
l=len(s)
sa=""
sb=""
for i in range(l):
    if i%2==0:
        sa+="0"
        sb+="1"
    else:
        sa+="1"
        sb+="0"
ca=0
cb=0
for i in range(l):
    if sa[i]!=s[i]:
        ca+=1
    if sb[i]!=s[i]:
        cb+=1
#print(ca)
#print(cb)
print(min(ca,cb))

D Problem

In diesem Problem können, wie Sie dem Experiment mit der Probe entnehmen können, ** n-mal Anweisungen verwendet werden, um die Situation für n aufeinanderfolgende Personen umzukehren **. Wenn Sie auf (Kenchons Artikel verweisen, ist es wahr, dass ** Operationen für sich überschneidende Abschnitte nicht schneidende Abschnitte sind. Sie können sehen, dass die Operation den gleichen Wert wie die Teilungsoperation hat **.) Daher wissen wir, dass wir die Gesamtzahl der Personen an k aufeinanderfolgenden Orten finden sollten, und wir können sehen, dass es gut wäre, die Personen an jedem aufeinanderfolgenden Ort nach Funktion zu einer mit der Gruppe zu kombinieren. Hier ist der Rückgabewert der Groupby-Funktion [[0, n1], [1, n2], ....] oder [[1, n1], [0, n2], ....] \ (Array G). , N1, n2 .... sind entweder (die Anzahl der aufeinanderfolgenden Personen). Um aufeinanderfolgende Personen an K Orten aus dem Array G zu nehmen, so dass die Gesamtzahl der aufeinanderfolgenden Personen groß wird, ist die Operation des Änderns von 0 in 1 äquivalent zu Contrarian, also beginnt sie mit ** 1 und endet mit 1. Sie können auch sehen, dass Sie 2K + 1-Elemente wie dieses aus dem Array G ** erhalten können. Das erste Muster des Rückgabewerts kann jedoch keine 2K + 1-Elemente abrufen, die mit 1 beginnen und mit 1 enden (einschließlich des ersten Elements), da das erste Element 0 ist. Wenn Sie also den K-Teil auswählen, der die erste 0 als zu ändernden Teil enthält, werden Sie an 2K-Elemente denken, die mit 0 beginnen und mit 1 enden (einschließlich des ersten Elements). Und danach können Sie ** auf das zweite Muster reduzieren, indem Sie bis auf die erste 0 ** nachdenken. Wenn Sie das zweite Muster betrachten, ** verschieben Sie die Elemente um zwei ** und ** das letzte Element kann 0 ** sein. In diesem Fall ist es daher erforderlich, die Fälle zu trennen. Vorsicht ist geboten. Wenn das Obige implementiert ist, wird es wie folgt. (Es war zu kompliziert und die Implementierung war eng und die Beurteilungsbedingungen wurden angemessen festgelegt, so dass das Debuggen lange dauerte.)

answerD.py

from sys import exit
#Groupby-Funktionsdefinition
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n,k=map(int,input().split())
s=list(input())
#Wenden Sie die Groupby-Funktion an"0"Wann"1"Notieren Sie, wie viele von ihnen in einer Reihe aufgereiht sind
x=groupby(s)
l=len(x)
#sum(y)Ich wollte es einfacher machen
y=[x[i][1] for i in range(l)]

#Reduziert auf das zweite Muster der Rückgabewerte der Groupby-Funktion
if x[0][0]=="0":
    su=sum(y[:2*k])
    ans=su
    y.pop(0)
    #Da es gelöscht wird, l-Vergiss es nicht
    l-=1
else:
    ans=0
#Erste 2k+Betrachten Sie die Summe von eins.(Da werden wir von hier aus nach der Skalierungsmethode zählen)
su=sum(y[:2*k+1])
#Vergessen Sie nicht, ans zu aktualisieren
ans=max(ans,su)
#Vergessen Sie nicht, durch 2 zu teilen, da Sie zwei Skalen nehmen
l_sub=(l-(2*k+1))//2
#2k+Es darf nicht mehr als eine geben, daher ist an dieser Stelle max bekannt.
if l_sub<=0:
    print(ans)
    exit()
#Nehmen Sie tatsächlich die Skala und folgen Sie dem letzten Element
for i in range(l_sub):
    #Nimm zwei Waagen
    su-=y[2*i]
    su-=y[2*i+1]
    su+=y[2*k+1+(2*i)]
    su+=y[2*k+1+(2*i+1)]
    ans=max(su,ans)
#Wenn das letzte Element 0 ist, sind die folgenden Bedingungen erfüllt
#Beachten Sie, dass es in diesem Fall mit 1 beginnt und mit 0 endet(Sie können zweimal subtrahieren und nur einmal addieren)
if 2*k+1+2*l_sub<l:
    su-=y[2*l_sub]
    su-=y[2*l_sub+1]
    su+=y[2*k+1+2*l_sub]
    ans=max(su,ans)
print(ans)