[PYTHON] AtCoderBeginnerContest177 Review & Summary (zweite Hälfte)

AtCoder ABC177 Dies ist eine Zusammenfassung der Probleme des AtCoder Beginner Contest 177, der am Samstag, den 29.08.2018, in der Reihenfolge von Problem A unter Berücksichtigung der Berücksichtigung stattfand. Die zweite Hälfte befasst sich mit dem DE-Problem. Klicken Sie hier für die erste Hälfte Das Problem wird zitiert, aber bitte überprüfen Sie die Wettbewerbsseite für Details. Klicken Sie hier für die Wettbewerbsseite Offizieller Kommentar PDF

D Problem Freunde

Problemstellung Es gibt $ N $ Personen von $ 1 $ bis $ N $ Personen. Sie erhalten $ M $ Informationen, dass "Personen $ A_i $ und Personen $ B_i $ Freunde sind". Die gleichen Informationen können mehrfach gegeben werden. Wenn $ X $ und $ Y $ Freunde sind und $ Y $ und $ Z $ Freunde sind, dann sind $ X $ und $ Z $ auch Freunde. Es gibt auch keine Freundschaften, die nicht aus $ M $ -Informationen abgeleitet werden können. Der böse Takahashi versucht, diese $ N $ Person in mehrere Gruppen aufzuteilen und eine Situation zu schaffen, in der jeder "keine Freunde in derselben Gruppe" hat. Wie viele Gruppen soll ich in ein Minimum aufteilen?

Indem wir die Verbindungen von Freunden verfolgen, untersuchen wir, wie viele Personen für jede Gruppe verbunden sind (= die Anzahl der im offiziellen Kommentar festgelegten Elemente des Freundes). Um zu verhindern, dass Freunde zur selben Gruppe gehören, benötigen wir mindestens eine Gruppe mit der größten Anzahl von Elementen in der Gruppe der Freunde. Dies ist die Antwort, die ausgegeben werden muss. Die Implementierung vermeidet doppelte Berechnungen, indem eine Liste erstellt und verwaltet wird, in der überprüft wird, ob Personen $ 1 $ zu Personen $ N $ zu einer Gruppe gehören.

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 Problem Coprime

Problemstellung Es gibt $ N $ Ganzzahlen. Die $ i $ -te Zahl ist $ A_i . Wenn " GCD (A_i, A_j) = 1 $ für alle $ 1 \ leq i <j \ leq N " gilt, wird { A_i } als paarweises Koprime bezeichnet. Wenn { A_i $} keine paarweise Koprime ist und $ GCD (A_1,…, A_N) = 1 , wird { A_i } als satzweise Koprime bezeichnet. Bestimmen Sie, ob { A_i $} paarweise Koprime, setweise Koprime oder keine ist. $ GCD (…) $ steht jedoch für die maximale Verpflichtung.

Ich konnte mir keinen Weg vorstellen, um die Primfaktorisierung zu beschleunigen. Überzeugt durch Sieben von Eratostenes im offiziellen Kommentar.

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")

Vielen Dank, dass Sie die zweite Hälfte bis zum Ende gelesen haben.