AtCoder ABC177 This is a summary of the problems of AtCoder Beginner Contest 177, which was held on Saturday, 2020-08-29, in order from problem A, taking into consideration the consideration. The second half deals with the DE problem. Click here for the first half The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF
Problem statement There are $ N $ people from $ 1 $ to $ N $ people. You will be given $ M $ information that "People $ A_i $ and Person $ B_i $ are friends". The same information may be given multiple times. If $ X $ and $ Y $ are friends and $ Y $ and $ Z $ are friends, then $ X $ and $ Z $ are also friends. Also, there are no friendships that cannot be derived from $ M $ information. Evil Takahashi is trying to divide this $ N $ person into several groups and create a situation where everyone has "no friends in the same group". How many groups should I divide into a minimum?
By tracing the connections of friends, we will investigate how many people are connected (= the number of elements of the friend set in the official commentary) for each group. In order to prevent friends from being in the same group, we need at least a group with the largest number of elements in the set of friends, which is the answer to be output. The implementation avoids duplication of calculations by creating and managing a list that checks whether people $ 1 $ to people $ N $ belong to some group.
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)
Problem statement There are $ N $ integers. The $ i $ th number is $ A_i
. When " GCD (A_i, A_j) = 1 $ for all $ 1 \ leq i <j \ leq N" holds, { A_i} is said to be pairwise coprime. When { A_i $} is not pairwise coprime and $ GCD (A_1,…, A_N) = 1, { A_i} is said to be setwise coprime. Determine if { A_i $} is pairwise coprime, setwise coprime, or neither. However, $ GCD (…) $ represents the greatest common divisor.
I couldn't think of a way to speed up the prime factorization. Convinced by sieving Eratosthenes in the official commentary.
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")
Thank you for reading the second half to the end.
Recommended Posts