I participated in AtCoder ABC177, so I will post it as a record.
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?
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")
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?
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)
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).
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)
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?
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