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.
A. Don't be late
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```.
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
S
from the beginning`s``` selected above matches the character string
`T``` S
and `` `T``` do not matchI 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.
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
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
is.
E. Coprime
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