AtCoder ABC177
2020-08-29(土)に行われたAtCoderBeginnerContest177の問題をA問題から順に考察も踏まえてまとめたものとなります．
後半ではDEの問題を扱います．前半はこちら
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF
D問題 Friends
問題文
人$1$から人$N$までの$N$人の人がいます。
「人$A_i$と人$B_i$は友達である」という情報が$M$個与えられます。同じ情報が複数回与えられることもあります。
$X$と$Y$が友達、かつ、$Y$と$Z$が友達ならば、$X$と$Z$も友達です。また、$M$個の情報から導くことができない友達関係は存在しません。
悪の高橋君は、この$N$人をいくつかのグループに分け、全ての人について「同じグループの中に友達がいない」という状況を作ろうとしています。
最小でいくつのグループに分ければ良いでしょうか？
友達の繋がりをたどって，何人と繋がりがあるのか（＝公式解説の友達集合の要素数）を，各まとまりごとに調べていく．
友達同士を同じグループに入れないようにするためには，少なくとも一番大きい友達集合の要素数のグループが必要となり，それが出力すべき答えとなる．
実装は，人$1$から人$N$がどこかのグループに属しているかどうか確認するlistを作成して管理することで，計算の重複をしないようにしている．
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問題 Coprime
問題文
$N$個の整数があります。$i$番目の数は$A_i$です。
「全ての$1 \leq i < j \leq N$について、$GCD(A_i,A_j)=1$」が成り立つとき、{$A_i$}は pairwise coprime であるといいます。
{$A_i$}が pairwise coprime ではなく、かつ、$GCD(A_1,…,A_N)=1$であるとき、{$A_i$}は setwise coprime であるといいます。
{$A_i$}が pairwise coprime、setwise coprime、そのどちらでもない、のいずれであるか判定してください。
ただし$GCD(…)$は最大公約数を表します。
素因数分解を高速でする方法が思いつかなかった．
公式解説のエラトステネスの篩みて納得．
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")
後半も最後まで読んでいただきありがとうございました．