AtCoderBeginnerContest177 Review & Summary (second semestre)

AtCoder ABC177 Ceci est un résumé des problèmes du concours AtCoder Beginner Contest 177, qui s'est déroulé le samedi 29/08/2020, dans l'ordre 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

Problème D Amis

Énoncé du problème Il y a des personnes $ N $ de 1 $ à $ N $ personnes. Vous recevrez des informations de $ M $ indiquant que "les personnes $ A_i $ et les personnes $ B_i $ sont des amis". La même information peut être donnée plusieurs fois. Si $ X $ et $ Y $ sont amis et que $ Y $ et $ Z $ sont amis, alors $ X $ et $ Z $ sont aussi amis. De plus, aucune amitié ne peut être dérivée des informations de $ M $. Evil Takahashi essaie de diviser cette personne $ N $ en plusieurs groupes et de créer une situation où tout le monde n'a «pas d'amis dans le même groupe». Combien de groupes dois-je diviser en un minimum?

En retraçant les connexions des amis, nous étudierons le nombre de personnes connectées (= le nombre d'éléments de l'ami défini dans le commentaire officiel) pour chaque groupe. Afin d'empêcher les amis de faire partie du même groupe, nous avons besoin d'au moins un groupe avec le plus grand nombre d'éléments dans l'ensemble d'amis, ce qui est la réponse à afficher. L'implémentation évite la duplication des calculs en créant et en gérant une liste qui vérifie si les personnes $ 1 $ aux personnes $ N $ appartiennent à un groupe.

abc177d.py


n, m = map(int, input().split())
set_dict = {}
chech_list = [0] * (n + 1)
for i in range(m):
    a, b = map(int, input().split())
    if a in set_dict:
        set_dict[a].add(b)
    else:
        set_dict[a] = {b}
    if b in set_dict:
        set_dict[b].add(a)
    else:
        set_dict[b] = {a}
    chech_list[a] = 1
    chech_list[b] = 1
ans = 1
for i in range(1, n + 1):
    if chech_list[i] == 0:
        continue
    count = 0
    temp_set = set_dict[i]
    while len(temp_set) > 0:
        x = temp_set.pop()
        count += 1
        chech_list[x] = 0
        for y in set_dict[x]:
            if chech_list[y] == 1:
                temp_set.add(y)
    ans = max(count, ans)
print(ans)

E problème Coprime

Énoncé du problème Il existe des entiers $ N $. Le $ i $ ème nombre est $ A_i . Quand " GCD (A_i, A_j) = 1 $ pour tout $ 1 \ leq i <j \ leq N " est maintenu, { A_i } est dit coprimaire par paires. Quand { A_i $} n'est pas coprime par paire et $ GCD (A_1,…, A_N) = 1 , { A_i } est dit coprimaire setwise. Déterminez si { A_i $} est coprime par paire, coprime setwise, ou aucun des deux. Cependant, $ GCD (…) $ représente l'engagement maximum.

Je ne pouvais pas penser à un moyen d'accélérer la factorisation principale. Convaincu en tamisant Eratostenes dans le commentaire officiel.

abc177e.py


def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
ans2 = a_list[0]
for i in range(1, n):
    ans2 = gcd(ans2, a_list[i])
    if ans2 == 1:
        break
if ans2 != 1:
    print("not coprime")
else:
    flag = 1
    max_a = a_list[n - 1] + 1
    num_flag_list = [True] * max_a
    d_list = list(range(0, max_a))
    d_list[0] = 1
    num_flag_list[0] = num_flag_list[1] = False
    for i in range(2, int(max_a**0.5) + 1):
        if num_flag_list[i]:
            for j in range(i**2, max_a, i):
                if num_flag_list[j] == True:
                    num_flag_list[j] = False
                    d_list[j] = i
    p_set = set()
    for a in a_list:
        if a == 1:
            continue
        temp_p_set = set()
        while True:
            p = d_list[a]
            if p not in temp_p_set:
                if p in p_set:
                    flag = 0
                    break
            temp_p_set.add(p)
            p_set.add(p)
            a = a // p
            if a == 1:
                break
        if flag == 0:
            break
    if flag == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Merci d'avoir lu la seconde moitié jusqu'à la fin.

Recommended Posts

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)
AtCoderBeginnerContest173 Review & Summary (second semestre)
AtCoderBeginnerContest177 Review & Summary (second semestre)
AtCoderBeginnerContest175 Review & Summary (premier semestre)
AtCoderBeginnerContest164 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)
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é