[PYTHON] AtCoder Past Question Review (12 / 6,7)

Ich werde die Probleme aufzeichnen, die ich in den letzten Fragen von AtCoder falsch gemacht habe, und die Probleme, die mich beeindruckt haben.

ABC102-C (Linear Approximation)

6WA, sah die Antwort

Setzen Sie zuerst $ B_i = A_i-i $ und sehen Sie sich dann die ganzzahlige Folge von $ B_i $ in der Reihenfolge von vorne an, und wenn Sie zwischen $ B_i-i und B_ {i + 1} - (i + 1) $ liegen Ich dachte darüber nach, ob es der Mindestwert in der Reihenfolge sein würde, aber ich sah die Antwort, weil die Fallklassifizierung der Grenze nicht gut lief und es die ganze Zeit WA war. (Ich möchte diese Methode in naher Zukunft AC.) Der Minimalwert der Summe der absoluten Werte wurde als Medianwert ** in die Antwort geschrieben, aber ich konnte ihn nicht gut verstehen, also habe ich ihn verstanden, indem ich die folgende Abbildung gezeichnet habe. (Wenn die Länge der Ganzzahlzeichenfolge 5 beträgt) Der rote Teil wird mehr gezählt als wenn der Medianwert b ist, aber Sie können sehen, dass der Medianwert sicherlich das Minimum ist.

answerC.py

n=int(input())
s=input().split()
#Es ist auch wichtig, die Problemstellung hier zu paraphrasieren
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

Da Sie nur zwei benachbarte tauschen können, ist es klar, dass das Wechseln von vorne am seltensten erfolgt? (Wie kann ich es beweisen ... ??) Wenn $ p_i = i $, tauschen Sie $ p_i $ und $ p_ {i + 1} $ aus, um $ p_i ≠ i $ zu erhalten, und wiederholen Sie i = 1 ~ n-1 in der Reihenfolge i <= n-1 Da $ p_i ≠ i $ ist, müssen Sie nur dann mit $ p_n $ und $ p_ {n-1} $ tauschen, wenn das letzte i = n $ p_i = i $ ist. ** Da zu diesem Zeitpunkt $ p_n = n $ ist, sollte beachtet werden, dass $ p_ {n-1} ≠ n-1 $ auch bei einem Austausch erfüllt ist. ** Als ich es löste, bemerkte ich die Präambel nicht und drehte die Schleife erneut mit i = n-1 ~ 1. (Es ist klar, dass beim Umlaufen nur $ p_n $ und $ p_ {n-1} $ Swaps auftreten ...)

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

Es ist kein schwieriges Problem, aber ich habe viele Fehler gemacht, weil ich falsch verstanden habe, dass die Farbe nur die Farbe in der Problemstellung ist, oder vergessen habe, nach dem Minimum und Maximum zu fragen. ** Ich möchte die Problemstellung richtig lesen, egal wie einfach es ist. ** ** ** Außerdem war der Code langweilig und schrecklich, also habe ich ihn umgeschrieben. ** Erhalten Sie keinen redundanten Code, es ist schwer zu lesen. ** ** **

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