[PYTHON] AtCoder Anfängerwettbewerb 177

AtCoder Anfängerwettbewerb 177

ABC177A - Don't be late

Brechen Sie in 2 Minuten durch. Schreiben Sie einfach.

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

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

ABC177B - Substring

Brechen Sie in 5 Minuten durch, vergessen Sie WA1. + 1 und sterben Sie. Überprüfen Sie, wie viele verschiedene Zeichen sich beim Verschieben befinden, und nehmen Sie den Mindestwert 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

Brechen Sie in 4 Minuten durch. Kumulative Summierung, da sie stirbt, wenn sie mit O (* N * ^{2 </ sup>) zu Naiv berechnet wird. Wenn Sie in der Reihenfolge von rechts vorgehen, wird die kumulative Summierung nicht durchgeführt, aber es ist in Ordnung.}

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)

Nachtrag: Ich habe versucht, es zu lösen, ohne die kumulative Summe zu verwenden.

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

Brechen Sie in 4 Minuten durch. Wie Sie sehen, Union Find. Sie müssen nur so viele Gruppen erstellen, wie die Anzahl der Personen, die zur größten Union gehören.

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

Es brach in 23 Minuten durch. Ich dachte, ich könnte gehen, wenn ich die Primfaktoren von rechts zerlegte. Ich hatte das Gefühl, ich könnte berechnen, ob es sich um eine festgelegte Koprime handelt oder nicht, aber es dauerte einige Zeit, weil die Leistung sank, also berechnete ich es separat.

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