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

Benötigte Zeit

スクリーンショット 2020-05-28 8.57.23.png

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.

IMG_0387.PNG

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

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 085 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 151 Rückblick auf frühere Fragen
AtCoder Beginner Contest 075 Rückblick auf frühere Fragen
AtCoder Beginner Contest 054 Rückblick auf frühere Fragen
AtCoder Beginner Contest 110 Rückblick auf frühere Fragen
AtCoder Beginner Contest 117 Rückblick auf frühere Fragen
AtCoder Beginner Contest 070 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 103 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