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

Benötigte Zeit

スクリーンショット 2020-01-13 13.13.28.png

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)

Recommended Posts

AtCoder Beginner Contest 102 Rückblick auf frühere Fragen
AtCoder Beginner Contest 072 Rückblick auf frühere Fragen
AtCoder Beginner Contest 062 Rückblick auf frühere Fragen
AtCoder Beginner Contest 113 Rückblick auf frühere Fragen
AtCoder Beginner Contest 074 Rückblick auf frühere Fragen
AtCoder Beginner Contest 051 Rückblick auf frühere Fragen
AtCoder Beginner Contest 127 Rückblick auf frühere Fragen
AtCoder Beginner Contest 119 Rückblick auf frühere Fragen
AtCoder Beginner Contest 054 Rückblick auf frühere Fragen
AtCoder Beginner Contest 117 Rückblick auf frühere Fragen
AtCoder Beginner Contest 105 Rückblick auf frühere Fragen
AtCoder Beginner Contest 112 Rückblick auf frühere Fragen
AtCoder Beginner Contest 076 Rückblick auf frühere Fragen
AtCoder Beginner Contest 089 Rückblick auf frühere Fragen
AtCoder Beginner Contest 069 Rückblick auf frühere Fragen
AtCoder Beginner Contest 079 Rückblick auf frühere Fragen
AtCoder Beginner Contest 056 Rückblick auf frühere Fragen
AtCoder Beginner Contest 087 Rückblick auf frühere Fragen
AtCoder Beginner Contest 067 Rückblick auf frühere Fragen
AtCoder Beginner Contest 093 Rückblick auf frühere Fragen
AtCoder Beginner Contest 046 Rückblick auf frühere Fragen
AtCoder Beginner Contest 123 Überprüfung früherer Fragen
AtCoder Beginner Contest 049 Rückblick auf frühere Fragen
AtCoder Beginner Contest 078 Rückblick auf frühere Fragen
AtCoder Beginner Contest 081 Rückblick auf frühere Fragen
AtCoder Beginner Contest 047 Rückblick auf frühere Fragen
AtCoder Beginner Contest 060 Rückblick auf frühere Fragen
AtCoder Beginner Contest 104 Rückblick auf frühere Fragen
AtCoder Beginner Contest 057 Rückblick auf frühere Fragen
AtCoder Beginner Contest 121 Rückblick auf frühere Fragen
AtCoder Beginner Contest 126 Rückblick auf frühere Fragen
AtCoder Beginner Contest 090 Rückblick auf frühere Fragen
AtCoder Beginner Contest 061 Rückblick auf frühere Fragen
AtCoder Beginner Contest 059 Rückblick auf frühere Fragen
AtCoder Beginner Contest 044 Rückblick auf frühere Fragen
AtCoder Beginner Contest 083 Rückblick auf frühere Fragen
AtCoder Beginner Contest 048 Rückblick auf frühere Fragen
AtCoder Beginner Contest 124 Rückblick auf frühere Fragen
AtCoder Beginner Contest 116 Rückblick auf frühere Fragen
AtCoder Beginner Contest 097 Rückblick auf frühere Fragen
AtCoder Beginner Contest 088 Rückblick auf frühere Fragen
AtCoder Beginner Contest 092 Rückblick auf frühere Fragen
AtCoder Beginner Contest 099 Rückblick auf frühere Fragen
AtCoder Beginner Contest 065 Rückblick auf frühere Fragen
AtCoder Beginner Contest 053 Rückblick auf frühere Fragen
AtCoder Beginner Contest 094 Rückblick auf frühere Fragen
AtCoder Beginner Contest 063 Rückblick auf frühere Fragen
AtCoder Beginner Contest 107 Rückblick auf frühere Fragen
AtCoder Beginner Contest 071 Rückblick auf frühere Fragen
AtCoder Beginner Contest 064 Rückblick auf frühere Fragen
AtCoder Beginner Contest 082 Rückblick auf frühere Fragen
AtCoder Beginner Contest 084 Rückblick auf frühere Fragen
AtCoder Beginner Contest 068 Rückblick auf frühere Fragen
AtCoder Beginner Contest 043 Rückblick auf frühere Fragen
AtCoder Beginner Contest 098 Rückblick auf frühere Fragen
AtCoder Beginner Contest 114 Rückblick auf frühere Fragen
AtCoder Beginner Contest 045 Rückblick auf frühere Fragen
AtCoder Beginner Contest 120 Rückblick auf frühere Fragen
AtCoder Beginner Contest 108 Rückblick auf frühere Fragen
AtCoder Beginner Contest 106 Rückblick auf frühere Fragen