[PYTHON] Concours de programmation Acing 2020
Les résultats de cette fois
Impressions
C'était le set le plus difficile de la classe ABC, c'était difficile.
D J'étais trop confus quant à la politique du problème et j'ai passé du temps, mais quand j'ai expérimenté, j'ai découvert que l'expérience est importante.
J'ai observé le problème E pendant un certain temps, mais je n'ai pas essayé la méthode gourmande. Je suis encore immature pour apprendre les bases des bases, donc je veux faire de mon mieux ... Je veux atteindre un niveau où je peux me qualifier de professionnel compétitif.
Problème A
Vous pouvez compter le nombre de multiples de D allant du plus petit multiple de D au-dessus de L au plus grand multiple de D en dessous de R.
Cela peut être reformulé comme ceil (l / d) * d, ceil (l / d) * d + d,…, floor (r / d) * d, donc le nombre est` floor (r / / d) -ceil (l / d) + 1 ».
A.py
from math import *
l,r,d=map(int,input().split())
print(floor(r/d)-ceil(l/d)+1)
Problème B
Tout ce que vous avez à faire est de vous assurer que le nombre de carrés écrits comme impairs est impair pour tous les nombres.
B.py
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
ans+=(i%2==0 and a[i]%2==1)
print(ans)
Problème C
J'ai soupçonné la factorisation pendant un moment, mais c'est difficile. Cependant, $ 1 \ leqq x \ leqq \ sqrt {n}, 1 \ leqq y \ leqq \ sqrt {n}, 1 \ leqq z \ leqq \ sqrt {n} $ a été immédiatement compris en regardant le terme carré. , Vous pouvez rechercher toutes les valeurs de $ x, y, z $ ($ O (N \ sqrt {N}) $ suffit).
Aussi, ce que vous voulez trouver est la valeur de $ f (1), f (2),…, f (n) $, qui est $ x ^ 2 + y ^ 2 + z ^ 2 + xy + yz pendant la recherche complète. Vous pouvez enregistrer la valeur de + zx $ de 1 $ à $ N $ un par un.
C.py
from math import *
n=int(input())
l=floor(sqrt(n))+1
ans=[0]*n
def f(a,b,c):
return a*a+b*b+c*c+a*b+b*c+c*a
for x in range(1,l+1):
for y in range(1,l+1):
for z in range(1,l+1):
g=f(x,y,z)
if g<=n:
ans[g-1]+=1
for i in range(n):
print(ans[i])
D problème
Cela a pris du temps à résoudre parce que je pensais au problème E. Il est difficile de choisir le problème à résoudre ... Si c'est un problème de classe ABC, j'aimerais faire un effort dans la mesure où je peux me le permettre.
Dans ce qui suit, le nombre donné par input est $ x $ et son popcount est $ c $.
Évidemment, même si vous implémentez popcount ** honnêtement, ce ne sera pas à temps ** car $ x $ sera un très grand nombre. Cependant, pour un certain nombre de $ K $, la valeur du popcount est d'environ $ \ log {K} $, donc en raison de la limitation du sujet, il ne faut qu'environ 5 fois pour répéter ** popcount à 0 ** ( Sous les contraintes du problème, on peut dire qu'il s'agit d'un multiple presque constant.)
Maintenant, pensons à trouver $ f (X_i) $ honnêtement pour $ 1 \ leqq i \ leqq N $, mais dans la première opération, il en coûte $ O (N) $ pour vérifier tous les chiffres. Le montant total du calcul coûte donc $ O (N ^ 2) $. (** Pensez honnêtement et réduisez ce gaspillage! **)
Cependant, ** $ f (X_i) $ ne change que le chiffre $ i $ **, alors considérez la différence due à l'inversion de ce chiffre après avoir économisé $ x $. De plus, si le chiffre $ i $ est $ 0 $, il passera à $ 1 $, donc ce nombre de popcount changera en $ c-1 $, et si le chiffre $ i $ est $ 1 $, il changera en $ 0 $, donc ce nombre de popcount changera. Cela devient $ c + 1 $, et il n'y a que ces deux façons.
Par conséquent, cette politique peut être réalisée en préparant les deux suivants dans le pré-calcul (notez qu'il est nécessaire de séparer complètement le cas de $ c-1 $ et le cas de $ c + 1 $ Est requis.).
$ i $ Un tableau qui stocke le reste de la différence lors du changement de chiffres $ m $
→
Ceux-ci peuvent être préparés par pré-calcul de $ O (N) $, chaque calcul de $ f (X_i) $ est $ O (1) $ pour le premier calcul de différence de popcount, et les popcount suivants sont pour popcount normal. Comme cela peut être fait avec un multiple constant de $ O (\ log {N}) $ en utilisant une fonction etc., il est possible de calculer avec $ O (N \ log {N}) $ au total, et même Python peut se le permettre. Vous pouvez le transmettre avec.
De plus, lorsque c devient 1, ** 0 division se produit **, il est donc nécessaire de l'éviter.
D.py
#Diviser par 0
import math
def popcount(x):
s=0
y=int(math.log2(x))+2
for i in range(y):
if(x>>i)&1:
s+=1
return x%s
n=int(input())
x=input()[::-1]
#Ce que je vais sortir
c=x.count("1")
#c+1 et c-Pensez juste à 1
#c=Division temporelle de 1
#m[i][j]:2^mod en pensant à i(c+j-1)
if c!=1:
m=[[1%(c-1),1%(c+1)]]
for i in range(n-1):
m.append([(2*m[-1][0])%(c-1),(2*m[-1][1])%(c+1)])
l=[0,0]
for i in range(n):
if x[i]=="1":
l[0]+=m[i][0]
l[1]+=m[i][1]
l[0]%=(c-1)
l[1]%=(c+1)
else:
m=[[1%(c+1),1%(c+1)]]
for i in range(n-1):
m.append([(2*m[-1][0])%(c+1),(2*m[-1][1])%(c+1)])
l=[0,0]
for i in range(n):
if x[i]=="1":
l[0]+=m[i][0]
l[1]+=m[i][1]
l[0]%=(c+1)
l[1]%=(c+1)
#Je veux en changer un seul, donc je veux le tout
#Utilisez popcount sauf pour la première fois
ans=[0]*n
for i in range(n):
if x[i]=="1":
if c-1==0:
ans[i]=0
continue
p=(l[0]+(c-1)-m[i][0])%(c-1)
ans[i]+=1
while p!=0:
p=popcount(p)
ans[i]+=1
else:
p=(l[1]+m[i][1])%(c+1)
ans[i]+=1
while p!=0:
p=popcount(p)
ans[i]+=1
ans=ans[::-1]
for i in range(n):
print(ans[i])
E problème
Il n'est pas possible d'utiliser une idée de court-circuit telle que choisir soit → $ 2 ^ N $ → DP, alors considérez d'abord la solution avec la méthode gloutonne **.
Ici, pour le $ i $ ème chameau, vous pouvez obtenir ** $ min (L_i, R_i) $ quel que soit l'ordre d'obtention de $ L_i ou R_i
Pendant le concours, je n'ai pu trouver l'idée que pour l'instant, mais ** Pensez au chameau qui veut choisir le côté gauche et au chameau qui veut choisir le côté droit ** (($ L_i-R_i, 0
En dessous, on peut dire que le chameau qui veut choisir le côté gauche et le chameau qui veut choisir le côté droit ** comment choisir la position du chameau n'interfèrent pas (indépendant) **. En effet, si le premier est un cercle rouge et le second est un cercle bleu, la position du chameau peut être déplacée comme indiqué sur la figure ci-dessous.
Par conséquent, dans ce qui suit, nous allons d'abord envisager de décider avec gourmandise de la position du chameau que vous souhaitez choisir sur le côté gauche. À ce stade, nous choisirons avec gourmandise parmi ceux avec le plus grand $ L_i-R_i $ (dans le $ K_i $ th), alors considérez la position optimale. ** La position optimale peut être reformulée comme la position qui ne nuit pas à la sélection des éléments suivants **. À ce stade, vous pouvez voir que le $ K_i $ th, qui a les positions les plus sélectionnables pour les autres chameaux après cela, est optimal. De plus, comme il n'y a pas de position que vous pouvez obtenir plus que cela lorsque vous la placez sur le côté gauche de ** $ K_i $ th, vous pouvez voir qu'elle est correcte à partir de cette idée. De plus, si $ K_i $ th est déjà sélectionné, vous pouvez sélectionner la position la plus à droite sur le côté gauche de celui-ci.
À partir de ce qui précède, enregistrez les positions non sélectionnées dans l'ordre croissant (utilisez l'ensemble), sélectionnez la position la plus grande sous $ K_i $ (à côté de l'un des éléments sélectionnés par upper_bound) comme position, puis supprimez-la de l'ensemble. Simplement fais-le. De plus, à ce stade, s'il n'y a pas de position correspondante, cet élément ne peut pas être sélectionné, alors considérez l'élément suivant. Ensuite, considérez cela non seulement sur le côté gauche, mais également sur le côté droit, et la somme de tous les éléments sélectionnés est la réponse.
Nouvelles découvertes sur la cupidité
→ ** Vous pouvez le déplacer dans une direction qui n'endommage pas **! !! Pour le dire autrement, considérez ** Y a-t-il un modèle qui peut être obtenu dans des cas autres que comment le déplacer **?
Problème F
Je vais sauter cette fois.
Recommended Posts