AtCoderBeginnerContest169 Review & Summary (second semestre)

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

D Problème Jeu Div

É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 1 → 1 2 → 3 3 → 6 4 → 10 5 → 15 C'est une séquence de nombres de différence. Si vous calculez cela, vous pouvez voir que le nombre de facteurs premiers $ p_1 $ requis pour opérer $ m $ fois est $ \ frac {m (m + 1)} {2} $, donc chaque décomposition en facteurs premiers J'ai pu obtenir la réponse en calculant combien de fois l'opération peut être effectuée pour le facteur premier et en l'additionnant.

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 $.

Problème E Nombre Médian

É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 $.

Un nombre impair de données

La réponse est $ D_ {(N + 1) / 2} --C_ {(N + 1) / 2} + 1 $.

Nombre pair de données

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

AtCoderBeginnerContest178 Review & Summary (second semestre)
AtCoderBeginnerContest161 Review & Summary (second semestre)
AtCoderBeginnerContest164 Review & Summary (second semestre)
AtCoderBeginnerContest176 Review & Summary (second semestre)
AtCoderBeginnerContest168 Review & Summary (second semestre)
AtCoderBeginnerContest169 Review & Summary (second semestre)
AtCoderBeginnerContest166 Review & Summary (second semestre)
AtCoderBeginnerContest171 Review & Summary (second semestre)
AtCoderBeginnerContest174 Review & Summary (second semestre)
AtCoderBeginnerContest173 Review & Summary (second semestre)
AtCoderBeginnerContest177 Review & Summary (second semestre)
AtCoderBeginnerContest175 Review & Summary (premier semestre)
AtCoderBeginnerContest169 Review & Summary (premier semestre)
AtCoderBeginnerContest174 Review & Summary (premier semestre)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest165 Review & Summary (premier semestre)
AtCoderBeginnerContest170 Review & Summary (premier semestre)
AtCoderBeginnerContest167 Review & Summary (premier semestre)
AtCoderBeginnerContest177 Review & Résumé (premier semestre)
AtCoderBeginnerContest168 Review & Summary (premier semestre)
AtCoderBeginnerContest178 Review & Summary (premier semestre)
AtCoderBeginnerContest171 Review & Summary (premier semestre)
AtCoderBeginnerContest166 Review & Summary (premier semestre)
AtCoderBeginnerContest161 Review & Summary (premier semestre)
AtCoderBeginnerContest172 Review & Summary (premier semestre)
AtCoderBeginnerContest176 Review & Summary (premier semestre)
AtCoderBeginnerContest180 Examen et résumé
AtCoderBeginnerContest181 Examen et résumé
AtCoderBeginnerContest182 Examen et résumé
AtCoderBeginnerContest183 Review & Résumé
AtCoderBeginnerContest179 Review & Résumé
Résumé du didacticiel Django Girls Première moitié