Benötigte Zeit

Impressionen

Diesmal konnte ich das D-Problem nicht lösen. Muster habe ich nicht viel gesehen

Problem A

Sie können den Fall danach teilen, ob n gerade ist oder nicht. Insbesondere wenn n gerade ist, sollte $ n $ ausgegeben werden, und wenn n ungerade ist, sollte $ n \ times 2 $ ausgegeben werden.

`answerA.py`


n=int(input())
print(n if n%2==0 else n*2)

B-Problem

Da Sie nur den absoluten Wert der maximalen Differenz ermitteln müssen, können Sie die Differenz zwischen den maximalen und minimalen Werten ermitteln.

`answerB.py`


n=int(input())
a=list(map(int,input().split()))
print(max(a)-min(a))

C-Problem

Hier ist das Unbekannte also $ b $

\begin{eqnarray}
abs(A_1-(b+1))+abs(A_2-(b+2))+…+abs(A_n-(b+n))=abs((A_1-1)-b)+abs((A_2-2)-b)+…+abs((A_n-n)-b)
\end{eqnarray}

Ich dachte über $ b $ nach, indem ich abs teilte. (** Trennung von Unbekannten! **)

Wenn Sie hier $ B_i = A_i-i $ setzen, kann diese Formel als $ abs (B_1-b) + abs (B_2-b) +… + abs (B_n-b) $ umgeschrieben werden. Darüber hinaus ändert das Sortieren der Sequenz $ B $ nicht den Wert von $ abs (B_1-b) + abs (B_2-b) +… + abs (B_n-b) $, also $ abs für die sortierte Sequenz B. Betrachten Sie den Maximalwert von (B_1-b) + abs (B_2-b) +… + abs (B_n-b) $.

Betrachten Sie zunächst, dass ** Ausdrücke, die Absolutwerte enthalten, Absolutwerte entfernen **, aber wie Absolutwerte entfernt werden, ist $ b \ leqq B_1, B_i \ leqq B_ {i + 1} (1 \ leqq i ) Da es für leqq n-1) und B_n \ leqq b $ unterschiedlich ist, betrachten Sie hier den Fall von $ b \ leqq B_1 $.

Unter diesem,

\begin{eqnarray}
abs(B_1-b)+abs(B_2-b)+…+abs(B_n-b)&=&(b-B_1)+(B_2-b)+…+(B_n-b)\\
&=&(B_1+B_2+…+B_n)+(2-n) \times b-2B_1
\end{eqnarray}

Es wird sein. Daher steigt für $ b $, wenn $ n \ geqq 2 $, monoton an und wird das Minimum bei $ b = B_1 $ (es kann leicht angezeigt werden, wenn $ n = 1 $).

In ähnlicher Weise zeigen auch $ B_i \ leqq B_ {i + 1} (1 \ leqq i \ leqq n-1) $ und $ B_n \ leqq b $ Monotonie innerhalb dieses Intervalls. Gute $ b $ Kandidaten sind $ B_1, B_2,…, B_n $.

Wir wissen, dass es $ n $ Kandidaten für $ b $ gibt und $ abs (B_1-b) + abs (B_2-b) +… + abs (B_n-b) $, die jedem $ b $ entsprechen, die Differenz ist. Es kann durch O (1) erhalten werden, indem man wie folgt denkt.

Dies wird ** sorgfältig implementiert, wobei auf die Handhabung des Index geachtet wird, wie unten gezeigt.

`answerC.py`


n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=(i+1)
a.sort()

m,now=sum(a)-2*a[0]+2*a[0]-a[0]*n,sum(a)-2*a[0]+2*a[0]-a[0]*n
for i in range(1,n):
    now=now-(2*(i)*a[i-1]-n*a[i-1])+(-2*a[i]+2*(i+1)*a[i]-n*a[i])
    m=min(now,m)

print(m)

D Problem

Es war schwierig mit einem Muster, das ich noch nie zuvor gemacht hatte. Immerhin habe ich es implementiert, nachdem ich die Antworten mehrerer Personen gesehen hatte. Auch in dieser Lösung wurde es als Skalierungsmethode geschrieben, aber ich bemerkte, dass es eine Konvexität hatte, also implementierte ich es mit einer dreiminütigen Suche **.

Wenn Sie es selbst implementieren, setzen Sie zuerst $ max (p, q, r, s) -min (p, q, r, s) $ auf $ k $ und $ p + q + r + s = $ ( Ich habe versucht, die Werte von $ p, q, r, s $ anhand der Summe der Zahlenspalten A) einzugrenzen, aber ich konnte nicht mehr Eckfälle eingrenzen, als ich erwartet hatte.

Als nächstes habe ich versucht, über die Größenordnung von 4 $ nachzudenken! $, Aber ich konnte es überhaupt nicht tun.

Aber ich habe vergessen, dass es hier eine typische Politik gibt. ** Wenn es mehrere Unbekannte gibt, denken Sie fest **. In diesem Problem gibt es drei Unbekannte (hier die Position, die die Unterspalte teilt). Lassen Sie uns also eine davon beheben.

Tatsächlich wird in solchen ** drei Mustern, wenn Sie die Mitte fixieren, der Abschnitt usw. verengt, so dass es einfacher ist, ** zu finden. Selbst bei diesem Problem wird die Sichtbarkeit sofort verbessert, wenn Sie die Partition in der Mitte reparieren.

Wenn die mittlere Partition als $ i (1 \ leqq i \ leqq n-1) $ th festgelegt ist, sollten $ p $ und $ q $, $ r $ und $ s $ so nahe wie möglich an $ max (p, p, Wenn Sie ein Diagramm zeichnen, können Sie sehen, dass q, r, s) -min (p, q, r, s) $ so klein wie möglich gemacht werden kann. Dies kann tatsächlich wie folgt bewiesen werden.

Daher werden wir im Folgenden erwägen, $ p $ und $ q $ so nah wie möglich zu bringen, aber $ r $ und $ s $ können auf die gleiche Weise betrachtet werden.

Wenn $ p $ und $ q $ so nahe wie möglich sind und das optimale $ p, q $ von der $ j (1 \ leqq j \ leqq i-1) $ -ten Partition begrenzt wird, dass ** Sie können sehen, dass $ max (p, q) -min (p, q) $ monoton ansteigt, wenn Sie eine Partition außerhalb der $ j $ -ten Partition auswählen (der Beweis hier ist selbstverständlich). Ich nicht.)

Daher kann gesagt werden, dass $ max (p, q) -min (p, q) $ Konvexität für den Index der Partition ** hat, so dass der beste Index für die Partition von $ p, q $ ** ist Sie können nach Trisektionssuche suchen ** (Ich werde die Trisektionssuche in einem anderen Artikel zusammenfassen).

Bei der Bestimmung des Index der Partition muss ** $ p, q $ mit $ O (1) $ ** berechnet werden. Dies ist jedoch **, die kumulative Summe wird zuerst berechnet und die Differenz wird berücksichtigt **. Sie können sofort danach fragen.

Wenn das Obige implementiert ist, wird es wie folgt. Es war ein schwieriges Problem, aber es war sehr informativ.

`answerD.py`


n=int(input())
a=list(map(int,input().split()))
s=[a[0]]
for i in range(1,n):
    s.append(s[-1]+a[i])

def f(c,i):
    global n,a,s
    return abs(s[c]-(s[i]-s[c]))

def g(c,i):
    global n,a,s
    return abs((s[c]-s[i])-(s[n-1]-s[c]))

ans=[]
for i in range(1,n-2):
    ans_=[]
    #Entscheide dich links
    l,r=0,i
    while l+2<r:
        c1=(l*2+r)//3
        c2=(l+2*r)//3
        if f(c1,i)>f(c2,i):
            l=c1
        else:
            r=c2
    x=sorted([(f(j,i),j) for j in range(l,r+1)])[0][1]
    ans_.append(s[x])
    ans_.append(s[i]-s[x])

    #Entscheide dich rechts
    l,r=i+1,n-1
    while l+2<r:
        c1=(l*2+r)//3
        c2=(l+2*r)//3
        if g(c1,i)>g(c2,i):
            l=c1
        else:
            r=c2
    x=sorted([(g(j,i),j) for j in range(l,r+1)])[0][1]
    ans_.append(s[x]-s[i])
    ans_.append(s[n-1]-s[x])

    ans.append(max(ans_)-min(ans_))
print(min(ans))

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