[PYTHON] AtCoder Beginner Contest 102 Revue des questions précédentes
Temps requis
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.
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