[PYTHON] Concours AtCoder Débutant 177

Concours AtCoder Débutant 177

ABC177A - Don't be late

Percer en 2 minutes. Il suffit d'écrire.

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

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

ABC177B - Substring

Passez en 5 minutes, oubliez WA1. + 1 et mourez. Vérifiez combien de caractères différents il y a pendant le décalage et prenez la valeur minimale 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

Percer dans 4 minutes. Somme cumulative car elle mourra si elle est calculée avec O (* N * ^{2 </ sup>) à Naive. Si vous allez dans l'ordre à partir de la droite, la somme cumulée ne sera pas effectuée, mais ce n'est pas grave.}

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: j'ai essayé de le résoudre sans utiliser la somme cumulée.

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

Percer en 4 minutes. Comme vous pouvez le voir, Union Find. Il vous suffit de créer autant de groupes que le nombre de personnes appartenant au plus grand syndicat.

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

Il a éclaté en 23 minutes. Je pensais que je pourrais y aller si je décomposais les facteurs premiers à partir de la droite. Je sentais que je pouvais calculer si c'était coprime ou non, mais cela prenait du temps parce que la performance chuterait, alors je l'ai calculée séparément.

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')