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 image.png

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)

image.png

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)

image.png

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 image.png

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 image.png

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.

Recommended Posts

AtCoder ABC 177 Python (A ~ E)
AtCoder ABC 178 Python (A ~ E)
AtCoder ABC 176 Python (A ~ E)
Template AtCoder ABC 179 Python (A ~ E)
AtCoder ABC 182 Python (A ~ D)
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
Solve Atcoder ABC176 (A, B, C, E) in Python
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
Solve AtCoder ABC166 with python
Atcoder ABC164 A-C in Python
Solve ABC176 E in Python
Atcoder ABC167 A-D in Python
Atcoder ABC165 A-D in Python
Atcoder ABC166 A-E in Python
Solve AtCoder ABC 186 with Python
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D in python
atCoder 173 Python
AtCoder ABC176
Review of atcoder ABC158, up to question E (Python)
AtCoder ABC177
Solve ABC163 A ~ C with Python
ABC127 A, B, C Explanation (python)
Solve ABC166 A ~ D with Python
ABC166 in Python A ~ C problem
Solve Atcoder ABC169 A-D in Python
Solve ABC168 A ~ C with Python
[Python] Now a brown coder ~ [AtCoder]
Solve ABC036 A ~ C in Python
Solved AtCoder ABC 114 C-755 with Python3
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
ABC128 A, B, C commentary (python)
Solve ABC158 A ~ C with Python
ABC126 A, B, C Explanation (python)
Solve ABC037 A ~ C in Python
[Python] I'm a green coder ~ [AtCoder]
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
AtCoder ABC168 A case expression solved in Ruby and Python
[AtCoder explanation] Control ABC164 A, B, C problems with Python!
[AtCoder explanation] Control ABC168 A, B, C problems with Python!
Beginner ABC156 (Python)
Solve ABC175 A, B, C in Python
[Python] [Explanation] AtCoder Typical DP Contest: A Contest
Python beginner Atcoder memo @ KEYENCE 2020, ABC problem
Beginner ABC155 (Python)
AtCoderBeginnerContest154 Participation memo (Python, A ~ E problem)
Solve ABC165 A, B, D in Python
Beginner ABC157 (Python)
Learn dynamic programming in Python (A ~ E)
[AtCoder explanation] Control the A, B, C problems of ABC182 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC186 with Python!