[PYTHON] AtCoder Beginner Contest 124 Revue des questions précédentes

Temps requis

Impressions

J'étais fatigué de faire des problèmes de 50 à 70, alors j'ai essayé un nombre complètement différent.

Problème A

En d'autres termes, appuyez toujours sur le plus grand

answerA.py

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

Problème B

Assurez-vous de pouvoir le voir depuis chaque auberge. Les cas doivent être classés selon qu'il existe ou non une auberge plus grande que cette auberge du côté de la mer.

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)

Problème C

Il est bon de ** faire attention à l'état final ** pour de tels problèmes du système de repeinture. Puisqu'il ne peut y avoir que 010101 ... ou 101010 ..., essayez les deux et résolvez celui avec un petit nombre de réécritures.

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))

Problème D

Dans ce problème, comme vous pouvez le voir à partir de l'expérience avec l'échantillon, ** n fois d'instructions peuvent être utilisées pour inverser la situation pour n personnes consécutives **. Si vous vous référez à (l'article de Kenchon, il est vrai que ** les opérations sur des sections qui se croisent sont des sections sans intersection. Vous pouvez voir qu'il s'agit de la même valeur ** que l'opération de fractionnement.) Par conséquent, il s'avère que le nombre total de personnes dans k lieux consécutifs doit être calculé, et il semble bon de combiner les personnes de chaque lieu continu en un seul avec le groupe par fonction. Ici, la valeur de retour de la fonction groupby est [[0, n1], [1, n2], ....] ou [[1, n1], [0, n2], ....] \ (array G). , N1, n2 .... se présentent sous la forme d'un nombre consécutif de personnes). De plus, afin de prendre des personnes consécutives dans K emplacements du tableau G de sorte que le nombre total de personnes consécutives devienne grand, l'opération consistant à changer 0 en 1 équivaut à contrarian, donc elle commence par ** 1 et se termine par 1. Vous pouvez également voir que vous pouvez récupérer 2K + 1 éléments du tableau G **. Cependant, le premier modèle de la valeur de retour ne peut pas récupérer les éléments 2K + 1 qui commencent par 1 et se terminent par 1 (y compris le premier élément) car le premier élément est 0. Donc, si vous choisissez la partie K qui contient le premier 0 comme partie à changer, vous penserez à 2K éléments qui commencent par 0 et se terminent par 1 (y compris le premier élément). Et après cela, vous pouvez ** réduire au deuxième modèle en pensant à l'exception du premier 0 **. En outre, lorsque vous considérez le deuxième modèle, ** décalez les éléments de deux ** et ** le dernier élément peut être 0 **, donc dans ce cas, il est nécessaire de séparer les cas. La prudence est de mise. Lorsque ce qui précède est mis en œuvre, cela devient comme suit. (Le débogage a pris beaucoup de temps parce que c'était trop compliqué et que la mise en œuvre était serrée et que les conditions de jugement étaient définies de manière appropriée.)

answerD.py

from sys import exit
#définition de la fonction groupby
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())
#Appliquer la fonction groupby"0"Quand"1"Enregistrez combien de chacun sont alignés dans une rangée
x=groupby(s)
l=len(x)
#sum(y)Je voulais faciliter les choses
y=[x[i][1] for i in range(l)]

#Réduit au deuxième modèle de valeurs de retour de la fonction groupby
if x[0][0]=="0":
    su=sum(y[:2*k])
    ans=su
    y.pop(0)
    #Puisqu'il sera supprimé, l-N'oubliez pas de
    l-=1
else:
    ans=0
#Premier 2k+Considérez la somme d'un.(Puisque nous compterons d'ici par la méthode de l'échelle)
su=sum(y[:2*k+1])
#N'oubliez pas de mettre à jour
ans=max(ans,su)
#N'oubliez pas de diviser par 2 car vous prendrez deux échelles
l_sub=(l-(2*k+1))//2
#2k+Il ne peut y en avoir plus d'un, donc à ce stade, max est connu.
if l_sub<=0:
    print(ans)
    exit()
#En fait, prenez l'échelle et suivez jusqu'au dernier élément
for i in range(l_sub):
    #Prenez deux échelles
    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)
#Si le dernier élément est 0, les conditions suivantes sont remplies
#Notez que dans ce cas, il commence par 1 et se termine par 0(Vous pouvez soustraire deux fois et ajouter une seule fois)
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)