AtCoder ABC177 A-D in python

AtCoder ABC177 I tried to solve the A-D problem with python.

I participated in AtCoder ABC177, so I will post it as a record.

A problem

Takahashi is meeting with Aoki. The meeting place is D meters away from Takahashi's house, and the meeting time is T minutes later. Mr. Takahashi will leave his house from now on and move straight to the meeting place at S meters per minute. Will you be in time for the meeting?

Thoughts

The maximum distance that Takahashi, who can move at S meters per minute, can move in T minutes is S * T. You can compare this value with D. (I got 1WA by mistake for the inequality sign ())

d, t, s = map(int, input().split())
if s*t >= d:
    print("Yes")
else:
    print("No")

B problem

Two strings S, T are given. Rewrite some letters of S so that T is a substring of S. At least how many characters do I need to rewrite?

Thoughts

From len (S)> = len (T), move the character string T in S, and the answer is the value obtained by subtracting the maximum number of matching characters from len (T).

s = input()
t = input()
sl = len(s)
tl = len(t)

cnt = 0
ans = 0

for i in range(sl-tl+1):
    for j in range(tl):
        if t[j] == s[i+j]:
            cnt += 1
    
    ans = max(cnt, ans)#ans:Maximum number of matching characters
    cnt = 0

print(tl - ans)

C problem

N integers A1,…, AN are given. Find the sum of Ai × Aj for all pairs (i, j) that satisfy 1 ≤ i <j ≤ N with mod (10 ** 9 + 7).

Thoughts

If you honestly double the for statement, it will be TLE rather than O (N ^ 2) ... When I wrote it out for the time being, I found the following. Consider the time of ex.i = 1, 2, .... Let sum = A1 + A2 + ... AN. When i = 1 A1 x A2 + A1 x A3 + A1 x A4 + ・ ・ ・ ・ + A1 x AN = A1 x (sum - A1) When i = 2 A2 x A3 + A2 x A4 + A2 x A5 + ・ ・ ・ ・ + A2 x AN = A2 x (sum - A1 - A2) If this is the case, it can be suppressed by O (N). If you implement this in Python,

n = int(input())
A = [0]+list(map(int, input().split()))
mod = 10**9 + 7
S = sum(A)
ans = 0

for i in range(1, n):
    ans += A[i]*(S-A[i])
    ans %= mod
    S -= A[i]

print(ans)

D problem

There are N people from 1 to N. You will be given M pieces of information that "People Ai and People Bi 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 pieces of information. Evil Takahashi is trying to divide these N people into several groups and create a situation where everyone has "no friends in the same group". How many groups should I divide at a minimum?

Thoughts

Just answer the maximum number of elements in the set with UnionFindTree. This is because it is sufficient to decompose the largest set and assign the elements of other sets to each element. You can understand the explanation of UnionFindTree by watching Katsuppa's video on Youtube. Problems with the string'Friend'are likely to be used with UnionFind ()

import sys
sys.setrecursionlimit(10 ** 9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+1)

    def find(self, x):#Search for parent elements
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])#Recursion
            return self.root[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        elif self.rank[x] > self.rank[y]:#Connected to a deep tree
            self.root[x] += self.root[y]
            self.root[y] = x#Let x be the parent of y

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def issame(self, x, y):#x,Determine if y is the same set
            return self.find(x) == self.find(y)

    
    def count(self, x):#Number of elements
        return (-1)*self.root[self.find(x)]

n, m = map(int, input().split())
uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a, b)

ans = 0

for i in range(n):
    ans = max(ans, uf.count(i))

print(ans)

Recommended Posts

Atcoder ABC167 A-D in Python
Atcoder ABC165 A-D in Python
AtCoder ABC177 A-D in python
Solve Atcoder ABC169 A-D in Python
Atcoder ABC164 A-C in Python
Atcoder ABC166 A-E in Python
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
Daily AtCoder # 36 in Python
Daily AtCoder # 2 in Python
Daily AtCoder # 32 in Python
Daily AtCoder # 6 in Python
Daily AtCoder # 53 in Python
Daily AtCoder # 33 in Python
Daily AtCoder # 7 in Python
Daily AtCoder # 37 in Python
Daily AtCoder # 8 in Python
Daily AtCoder # 21 in Python
Daily AtCoder # 38 in Python
Daily AtCoder # 11 in Python
Daily AtCoder # 15 in Python
Daily AtCoder # 47 in Python
Daily AtCoder # 13 in Python
Daily AtCoder # 45 in Python
Daily AtCoder # 30 in Python
Daily AtCoder # 10 in Python
Daily AtCoder # 28 in Python
Daily AtCoder # 20 in Python
Daily AtCoder # 19 in Python
Daily AtCoder # 52 in Python
Daily AtCoder # 3 in Python
Daily AtCoder # 50 in Python
Daily AtCoder # 26 in Python
Daily AtCoder # 4 in Python
Daily AtCoder # 43 in Python
Daily AtCoder # 29 in Python
Daily AtCoder # 22 in Python
Daily AtCoder # 27 in Python
Daily AtCoder # 1 in Python
Solve ABC169 in Python
Daily AtCoder # 25 in Python
Daily AtCoder # 16 in Python
Daily AtCoder # 12 in Python
Daily AtCoder # 48 in Python
Daily AtCoder # 23 in Python
Daily AtCoder # 34 in Python
Daily AtCoder # 51 in Python
Daily AtCoder # 31 in Python
Daily AtCoder # 46 in Python
Daily AtCoder # 35 in Python
Daily AtCoder # 44 in Python
Daily AtCoder # 41 in Python
AtCoder ABC 177 Python (A ~ E)
Solve AtCoder ABC166 with python
AtCoder ABC 178 Python (A ~ E)
Solve ABC176 E in Python
Python Input Note in AtCoder
AtCoder ABC 176 Python (A ~ E)
Solve ABC175 D in Python