AtCoder ABC 177 Python (A ~ E)

Summary

Only A and D were solved. I got stuck in B and couldn't solve C ... The only salvation was that D was solved immediately. I couldn't advance to E due to the time loss of B and C. It was a disappointing result.

problem

AtCoder Beginner Contest 177

A. Don't be late

Answer

D, T, S = map(int, input().split())

time = D / S
if T < time:
    print('No')
else:
    print('Yes')

Find the time `time``` when traveling D``` meters at speed `` `` S``` and compare it with the time limit `` T```.

B. Substring (AC at a later date)

Answer

S = input()
T = input()

answer = float('inf')
for s in range(len(S)):
    if len(S) - s < len(T):
        break

    count = 0
    for t in range(len(T)):
        if S[s+t] != T[t]:
            count += 1
            
    answer = min(answer, count)

print(answer)

The policy is

1. Try all the strings S from the beginning
2. Judge that the subscript `s``` selected above matches the character string `T```
3. Count the number of subscripts where S and `` `T``` do not match
4. Repeat steps 1 and 2 and take `` `min``` to answer is.

I thought too hard at the time of the contest. The above answer example counts `S``` as the main, but at the time of the contest, I tried to count with `T``` as the main and it did not work.

C. Sum of product of pairs (AC at a later date)

Answer

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

sq_sum = sum(map(lambda x: x*x, A))
sum_sq = sum(A) * sum(A)
answer = (sum_sq - sq_sum) // 2

print(answer % mod)

It is easy if you notice the following formula transformation.

(A_1 + A_2 + .... + A_n)^2 = (A_1^2 + A_2^2 + .... + A_n^2) + 2(A_1A_2 + A_2A_3 + .... + A_{n-1}A_n)\\

(A_1A_2 + A_2A_3 + .... + A_{n-1}A_n) = ((A_1 + A_2 + .... + A_n)^2 - (A_1^2 + A_2^2 + .... + A_n^2)) \div 2

The list A is "squared and summed" as `sq_sum```, and the "total and squared" is found as `sum_sq```. Take the difference and divide by 2.

D. Friends

Answer

class UnionFind(): #0 index
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]


if __name__ == "__main__":
    N, M = map(int, input().split()) #N people, M relationships
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    answer = 0
    for i in range(N):
        answer = max(answer, union_find.size(i))

    print(answer)
   

The only template I have prepared for Union Find was helpful. In order to create a group so that there are no friends in the same group, it seems that the group members with the largest friendship should be separated.

The policy is

1. Manage group attributes with UnionFind
2. Check the size of each group
3. The largest group size is the answer

is.

E. Coprime

Answer (AC at a later date)

import math
L = 10**6 + 1

N = int(input())
A = list(map(int, input().split()))
memo = [0] * L
flag = 0 #0 pairwise coprime

for a in A:
    memo[a] += 1

for i in range(2, L): #A gcd of 1 in all is the same as no number in the step for each number of interest.
    if sum(memo[i::i]) > 1:
        flag = 1
        break

g = 0
for i in range(N):
    g = math.gcd(g, A[i])

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)

There are two things to do: "take a GCD for every pair and check if it's 1" and "take a GCD for every A and check if it's 1". is. You can do the second one without thinking about it, but you need to devise the first one.

If you take GCD for all pairs, it will be `TLE```, so consider a different approach. If the GCD is 1, it means that the number that is a multiple of A that came out once does not come out, so check it. Specifically, count the number of occurrences of the A``` element in the `` memo array, add `` `memo to each subscript step, and add `. Take `` sum```.

After that, pay attention to the conditional branching of "pairwise coprime", "setwise coprime", and "not coprime" and output the answer.