[PYTHON] Examen des questions passées d'AtCoder (12 / 6,7)

Je garderai une trace des problèmes que j'ai commis une erreur dans les questions passées d'AtCoder et des problèmes qui m'ont laissé une impression.

ABC102-C (Linear Approximation)

6WA, j'ai vu la réponse

Tout d'abord, définissez $ B_i = A_i-i $, puis regardez la séquence entière de $ B_i $ dans l'ordre de l'avant, et lorsque vous êtes entre $ B_i-i et B_ {i + 1} - (i + 1) $ Je me suis demandé si ce serait la valeur minimale dans l'ordre, mais j'ai vu la réponse parce que la classification des cas de la frontière ne se passait pas bien et c'était WA tout le temps. (Je voudrais AC cette méthode dans un proche avenir.) ** La valeur minimale de la somme des valeurs absolues a été écrite dans la réponse comme valeur médiane **, mais je ne pouvais pas bien la comprendre, donc je l'ai comprise en dessinant la figure ci-dessous. (Lorsque la longueur de la chaîne entière est 5) La partie rouge est plus comptée que lorsque la valeur médiane est b, mais vous pouvez voir que la valeur médiane est certainement la valeur minimale.

answerC.py

n=int(input())
s=input().split()
#Il est également important de paraphraser l'énoncé du problème ici
a=sorted([int(s[i])-i-1 for i in range(n)])

c=0
for i in range(n):
    if i<=n//2:
        c+=(a[n//2]-a[i])
    else:
        c+=(a[i]-a[n//2])
print(c)

ABC72-D(Derangement)

2WA

Puisque vous ne pouvez échanger que deux éléments adjacents, est-il clair que l'échange par l'avant est le moins de fois possible? (Comment puis-je le prouver ... ??) Quand $ p_i = i $, échangez $ p_i $ et $ p_ {i + 1} $ pour faire $ p_i ≠ i $, et répétez i = 1 ~ n-1 dans l'ordre, i <= n-1 Puisque $ p_i ≠ i $, vous n'avez besoin d'échanger avec $ p_n $ et $ p_ {n-1} $ que lorsque le dernier i = n est $ p_i = i $. ** De plus, puisque $ p_n = n $ à ce moment, il convient de noter que même s'il est échangé, $ p_ {n-1} ≠ n-1 $ sera satisfait. ** De plus, quand je le résolvais, je n'ai pas remarqué le préambule et je faisais à nouveau tourner la boucle avec i = n-1 ~ 1. (Il est clair que lorsque vous faites une boucle, seuls les échanges $ p_n $ et $ p_ {n-1} $ se produisent ...)

answerD_bad.py

n=int(input())
f=list(map(int,input().split()))
c=0
for i in range(n-1):
    if f[i]==i+1:
        c+=1
        f[i],f[i+1]=f[i+1],f[i]

for i in range(n-1,0,-1):
    if f1[i]==i+1:
        c+=1
        f[i],f[i-1]=f[i-1],f[i]

print(c)

answerD_good.py

n=int(input())
f=list(map(int,input().split()))
c=0
for i in range(n-1):
    if f[i]==i+1:
        c+=1
        f[i],f[i+1]=f[i+1],f[i]
if f[n-1]==n:
    
print(c)

ABC064-C

3WA,2RE

Ce n'est pas un problème difficile, mais j'ai fait beaucoup d'erreurs parce que j'ai mal compris qu'il n'y avait que les couleurs dans l'énoncé du problème, et j'ai oublié de demander le minimum et le maximum. ** Je veux lire correctement l'énoncé du problème, aussi simple soit-il. ** ** De plus, le code était fastidieux et terrible, alors je l'ai réécrit. ** N'obtenez pas de code redondant, c'est difficile à lire. ** **

answerC_bad.py

n=int(input())
a=sorted(list(map(int,input().split())))
c=[0]*8
k=n
for i in range(n):
    if a[i]<400:
        c[0]=1
    elif a[i]<800:
        c[1]=1
    elif a[i]<1200:
        c[2]=1
    elif a[i]<1600:
        c[3]=1
    elif a[i]<2000:
        c[4]=1
    elif a[i]<2400:
        c[5]=1
    elif a[i]<2800:
        c[6]=1
    elif a[i]<3200:
        c[7]=1
    else:
        k=i
        break

d=0
for i in range(8):
    if c[i]==1:
        d+=1
if d==0:
    print(1, end=" ")
else:
    print(d, end=" ")

print(d+(n-k))

answerC_good.py

n=int(input())
a=sorted(list(map(int,input().split())))
c=[0]*8
k=n
for i in range(n):
    for j in range(8):
        if 400*j<=a[i]<400*(j+1):
            c[j]=1
            break
    else:
        k=i
        break

d=c.count(1)
if d==0:
    print(1, end=" ")
else:
    print(d, end=" ")

print(d+(n-k))