[PYTHON] AtCoder Beginner Contest 177

AtCoder Beginner Contest 177

ABC177A - Don't be late

Break through in 2 minutes. Just write.

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

if D > S * T:
    print('No')
else:
    print('Yes')

ABC177B - Substring

Break through in 5 minutes, forget WA1. + 1 and die. Check how many different characters there are while shifting, and take the minimum value OK.

S = input()
T = input()

result = float('inf')
for i in range(len(S) - len(T) + 1):
    t = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            t += 1
    result = min(result, t)
print(result)

ABC177C - Sum of product of pairs

It breaks through in 4 minutes. If you calculate with O (* N * ^{2 </ sup>) for naive, you will die, so you add up the cumulative total.}

from itertools import accumulate

m = 1000000007

N, *A = map(int, open(0).read().split())

result = 0
b = list(accumulate(A))
for i in range(N):
    result += A[i] * (b[N - 1] - b[i])
    result %= m
print(result)

Postscript: I tried to solve it without using the cumulative sum.

m = 1000000007

N, *A = map(int, open(0).read().split())

result = 0
a = 0
for i in range(1, N + 1):
    result += a * A[N - i]
    a += A[N - i]
    result %= m
print(result)

ABC177D - Friends

Break through in 4 minutes. As you can see, Union Find. You only have to create as many groups as the number of people belonging to the largest union.

from sys import setrecursionlimit, stdin


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


readline = stdin.readline
setrecursionlimit(10 ** 6)

N, M = map(int, readline().split())

parent = [-1] * N
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, readline().split())
    unite(parent, A, B)

print(-min(parent))

ABC177E - Coprime

It broke through in 23 minutes. I thought that I could go by factoring the prime factors from the right. I felt that I could calculate whether it was setwise coprime or not, but it took time because the performance dropped, so I calculated it separately.

from math import gcd
from functools import reduce


def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e))
    return result


def f():
    s = set()
    for i in range(N - 1, -1, -1):
        t = prime_factorize(A[i])
        for p, _ in t:
            if p in s:
                return False
            s.add(p)
    return True


N, *A = map(int, open(0).read().split())

prime_table = make_prime_table(10 ** 6)
if f():
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')