AtCoder ABC169 Ceci est un résumé des problèmes de AtCoder Beginner Contest 169 qui s'est tenu le 2020-05-31 (dim), en partant du problème A, en tenant compte de la considération. La seconde partie traite du problème de l'ED. Cliquez ici pour la première moitié. Le problème est cité, mais veuillez consulter la page du concours pour plus de détails. Cliquez ici pour la page du concours Commentaire officiel PDF
Énoncé du problème Un entier positif $ N $ est donné. Pensez à répéter les opérations suivantes pour $ N $. ・ Tout d'abord, sélectionnez un entier positif $ z $ qui satisfait toutes les conditions suivantes. ◦ Peut être exprimé comme $ z = p ^ e $ en utilisant un certain nombre premier $ p $ et un entier positif $ e $ ◦ $ N $ est divisible par $ z $ ◦ Différent de tout entier sélectionné lors de l'opération précédente ・ Remplacez $ N $ par $ N / z $ Découvrez combien de fois vous pouvez effectuer l'opération.
Pour le moment, je me suis rendu compte que ce problème pouvait être facilement résolu en factorisant les facteurs premiers, j'ai donc recherché les articles auxquels j'ai toujours été redevable et j'ai copié le code de la partie factorisation.
Factorisation prime rapide avec Python-pour les professionnels de la concurrence-
Le problème cette fois est que si vous avez $ k $ d'un certain facteur premier $ p_1 $, vous devez penser au nombre d'opérations que vous pouvez effectuer, mais au nombre d'opérations → le nombre de facteurs premiers requis $ p_1 $ Est
abc169d.py
def factorization(n):
arr = []
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
if temp%i==0:
cnt=0
while temp%i==0:
cnt+=1
temp //= i
arr.append([i, cnt])
if temp!=1:
arr.append([temp, 1])
if arr==[]:
arr.append([n, 1])
return arr
n = int(input())
if n == 1:
print(0)
else:
x_list = factorization(n)
ans = 0
for x in x_list:
n = 2
while True:
if x[1] < (n * n + n) // 2:
ans += n - 1
break
n += 1
print(ans)
Vous devez faire attention uniquement lorsque l'entrée est de 1 $.
Énoncé du problème Il y a $ N $ entiers $ X_1, X_2, ⋯, X_N $, que nous savons être $ A_i \ leq X_i \ leq B_i $. Découvrez combien de valeurs médianes possibles pour $ X_1, X_2, ⋯, X_N $.
Je n'ai pas pu arriver à temps car j'étais trop occupé par les problèmes B et C, mais j'ai rapidement réalisé que je pouvais le résoudre en triant $ A $ et $ B $ séparément et en utilisant leurs valeurs médianes. Le temps est écoulé en écrivant le code jusqu'à ce que le nombre de données soit impair.
Concernant le problème, commencez par trier $ A_1, A_2, ..., A_N $, et la séquence résultante est $ C_1, C_2, ..., C_N $ et $ B_1, B_2, ..., B_N $ sont triés. En conséquence, la séquence résultante est $ D_1, D_2, ..., D_N $.
La réponse est $ D_ {(N + 1) / 2} --C_ {(N + 1) / 2} + 1 $.
La réponse est $ D_ {N / 2} --C_ {N / 2} + D_ {N / 2 + 1} --C_ {N / 2 + 1} + 1 $. Par exemple, si $ C_ {N / 2} = 5, C_ {N / 2 + 1} = 7, D_ {N / 2} = 7, D_ {N / 2 + 1} = 9 $, les combinaisons possibles sont ，
| 5 | 6 | 7 | |
|---|---|---|---|
| 7 | 6 | 13/2 | 7 |
| 8 | 13/2 | 7 | 15/2 |
| 9 | 7 | 15/2 | 8 |
La réponse est 6,13 $ / 2,7,15 / 2,8 $, soit 5 $. Puisque cette réponse est le nombre de lignes + le nombre de colonnes du tableau -1, la même réponse peut être obtenue par la formule ci-dessus.
abc169e.py
n = int(input())
a_list = []
b_list = []
for i in range(0, n):
a, b = map(int, input().split())
a_list.append(a)
b_list.append(b)
a_list.sort()
b_list.sort()
if n % 2 == 0:
x1 = n // 2 - 1
x2 = n // 2
print(b_list[x2] - a_list[x2] + b_list[x1] - a_list[x1] + 1)
else:
x = n // 2
print(b_list[x] - a_list[x] + 1)
Si le problème posé de A à C est le niveau de difficulté habituel, je pense que j'aurais pu en terminer 5, mais je ressens un manque d'étude. Au moment où j'ai trouvé un emploi, j'ai commencé à penser que je devrais améliorer mes compétences en programmation autant que possible, donc je sens que cela convient à mon objectif, alors j'aimerais continuer à participer (je ne peux pas passer les problèmes B et C, Si le taux baissait, je devrais garder une distance). Je suis occupé cette semaine avec le problème F, donc j'aimerais l'ajouter même quand j'en ai le temps.
Merci d'avoir lu la seconde moitié jusqu'à la fin.
Recommended Posts