AtCoder Beginner Contest 102 Revue des questions précédentes

Temps requis

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

Impressions

Je n'ai pas pu résoudre le problème D cette fois. Des motifs que je n'ai pas beaucoup vus

Problème A

Vous pouvez diviser le cas selon que n est pair ou non. Plus précisément, si n est pair, $ n $ doit être affiché, et si n est impair, $ n \ times 2 $ doit être affiché.

answerA.py


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

Problème B

Comme il vous suffit de trouver la valeur absolue de la différence maximale, vous pouvez trouver la différence entre les valeurs maximale et minimale.

answerB.py


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

Problème C

Ici, l'inconnu est $ b $, donc

\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}

J'ai pensé à $ b $ en divisant les abdos. (** Séparation des inconnues! **)

Ici, si vous définissez $ B_i = A_i-i $, cette formule peut être réécrite comme $ abs (B_1-b) + abs (B_2-b) +… + abs (B_n-b) $. De plus, le tri de la séquence $ B $ ne change pas la valeur de $ abs (B_1-b) + abs (B_2-b) +… + abs (B_n-b) $, donc $ abs pour la séquence triée B Considérons la valeur maximale de (B_1-b) + abs (B_2-b) +… + abs (B_n-b) $.

Tout d'abord, considérons que ** les expressions qui incluent des valeurs absolues suppriment les valeurs absolues **, mais comment supprimer les valeurs absolues est $ b \ leqq B_1, B_i \ leqq B_ {i + 1} (1 \ leqq i ) Puisqu'il est différent pour leqq n-1) et B_n \ leqq b $, considérons le cas de $ b \ leqq B_1 $ ici.

Sous ceci,

\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}

Ce sera. Par conséquent, pour $ b $, quand $ n \ geqq 2 $, il augmente de façon monotone et devient le minimum à $ b = B_1 $ (il peut être facilement montré quand $ n = 1 $).

De même, $ B_i \ leqq B_ {i + 1} (1 \ leqq i \ leqq n-1) $ et $ B_n \ leqq b $ montrent également la monotonie dans cet intervalle. Les bons candidats $ b $ sont $ B_1, B_2,…, B_n $.

On sait qu'il y a $ n $ candidats pour $ b $, et $ abs (B_1-b) + abs (B_2-b) +… + abs (B_n-b) $ correspondant à chaque $ b $ est la différence. Il peut être obtenu par O (1) en pensant comme suit.

Ceci est ** soigneusement mis en œuvre tout en prêtant attention à la gestion de l'index, comme indiqué ci-dessous.

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)

Problème D

C'était difficile avec un modèle que je n'avais jamais fait auparavant. Après tout, je l'ai implémenté après avoir vu les réponses de plusieurs personnes. De plus, dans cette solution, elle a été écrite comme méthode d'échelle, mais j'ai remarqué qu'elle avait une convexité, alors je l'ai implémentée avec une recherche de trois minutes **.

Tout d'abord, lorsque vous l'implémentez vous-même, définissez $ max (p, q, r, s) -min (p, q, r, s) $ à $ k $ et $ p + q + r + s = $ ( J'ai essayé de réduire les valeurs de $ p, q, r, s $ en utilisant la somme des colonnes numériques A), mais je ne pouvais pas réduire plus de cas de coin que prévu.

Ensuite, j'ai essayé de penser à l'ordre de taille de 4 $! $, Mais je ne pouvais pas du tout le faire.

Mais j'ai oublié qu'il y a une politique typique ici. ** S'il y a plusieurs inconnues, pensez fixement **. Dans ce problème, il y a trois inconnues (ici, la position qui divise la sous-colonne), corrigeons donc l'une d'entre elles.

En fait, dans ces ** trois modèles, si vous fixez le centre, la section, etc. sera rétrécie, donc elle sera plus facile à trouver **. Même dans ce problème, si vous corrigez la partition au milieu, la visibilité s'améliorera immédiatement.

Lorsque la partition du milieu est fixée comme $ i (1 \ leqq i \ leqq n-1) $ th, $ p $ et $ q $, $ r $ et $ s $ doivent être aussi proches que possible de $ max (p, p, Si vous dessinez un diagramme, vous pouvez voir que q, r, s) -min (p, q, r, s) $ peut être rendu aussi petit que possible. Cela peut en fait être prouvé comme suit.

IMG_0387.PNG

Par conséquent, dans ce qui suit, nous envisagerons de rendre $ p $ et $ q $ aussi proches que possible, mais $ r $ et $ s $ peuvent être considérés à peu près de la même manière.

De plus, lorsque $ p $ et $ q $ sont aussi proches que possible, lorsque le $ p optimal, q $ est bordé par la partition $ j (1 \ leqq j \ leqq i-1) $ ème, cela ** Vous pouvez voir que $ max (p, q) -min (p, q) $ augmente de manière monotone lorsque vous choisissez une partition éloignée de la partition $ j $ th (la preuve ici est évidente) Je ne.)

Par conséquent, on peut dire que $ max (p, q) -min (p, q) $ a une convexité pour l'index de la partition **, donc le meilleur index pour la partition de $ p, q $ est ** Vous pouvez effectuer une recherche par recherche par trisection ** (je résumerai la recherche par trisection dans un autre article).

De plus, lors de la détermination de l'indice de la partition, ** $ p, q $ doit être calculé par $ O (1) $ **, mais c'est ** la somme cumulée est calculée en premier et la différence est considérée **. Vous pouvez le demander immédiatement.

Lorsque ce qui précède est mis en œuvre, cela devient comme suit. C'était un problème difficile, mais très instructif.

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_=[]
    #Décidez à gauche
    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])

    #Décidez de la bonne
    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 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes