AtCoder ABC 177 Python (A ~ E)

Zusammenfassung

Nur A und D wurden gelöst. Ich blieb in B stecken und konnte C nicht lösen ... Die einzige Rettung war, dass D sofort gelöst wurde. Ich konnte wegen des Zeitverlusts von B und C nicht zu E vorrücken. Es war ein enttäuschendes Ergebnis.

Problem

AtCoder Beginner Contest 177

A. Don't be late

Antworten

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

time = D / S
if T < time:
    print('No')
else:
    print('Yes')

Finden Sie die Zeit `Zeit```, wenn Sie` D Meter mit Geschwindigkeit` `` S fahren und vergleichen Sie sie mit dem Zeitlimit `` `T```.

B. Teilstring (Wechselstrom zu einem späteren Zeitpunkt)

Antworten

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)

Die Politik ist

1. Probieren Sie alle Saiten `` `S``` von Anfang an aus
2. Beurteilen Sie, dass der oben ausgewählte Index `s``` mit der Zeichenkette` T``` übereinstimmt
3. Zählen Sie die Anzahl der Indizes, bei denen `S``` und` T``` nicht übereinstimmen
4. Wiederholen Sie die Schritte 1 und 2 und antworten Sie mit `` `min``` ist.

Ich habe zum Zeitpunkt des Wettbewerbs zu viel nachgedacht. Das obige Antwortbeispiel zählt `S``` als Haupt, aber zum Zeitpunkt des Wettbewerbs habe ich versucht, mit` T``` als Haupt zu zählen und es hat nicht funktioniert.

C. Summe der Produktpaare (AC zu einem späteren Zeitpunkt)

Antworten

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)

Es ist einfach, wenn Sie die folgende Formelumwandlung bemerken.

(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

Die Liste `A``` wird als` sq_sum berechnet, und die "Summe und Quadrat" wird als `` `sum_sq berechnet. Nehmen Sie die Differenz und teilen Sie durch 2.

D. Friends

Antworten

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 Personen, M Beziehungen
    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)
   

Die einzige "UnionFind" -Vorlage, die ich vorbereitet habe, war nützlich. Um eine Gruppe so zu erstellen, dass sich keine Freunde in derselben Gruppe befinden, sollten die Gruppenmitglieder mit der größten Freundschaft getrennt werden.

Die Politik ist

1. Verwalten Sie Gruppenattribute mit Union Find
2. Überprüfen Sie die Größe jeder Gruppe
3. Die größte Gruppengröße ist die Antwort

ist.

E. Coprime

Antwort (AC zu einem späteren Zeitpunkt)

import math
L = 10**6 + 1

N = int(input())
A = list(map(int, input().split()))
memo = [0] * L
flag = 0 #0 paarweise Koprime

for a in A:
    memo[a] += 1

for i in range(2, L): #Eine gcd von insgesamt 1 ist die gleiche wie keine Zahl im Schritt für jede interessierende Zahl
    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)

Es gibt zwei Dinge zu tun: "Nehmen Sie eine GCD für alle Paare und prüfen Sie, ob es 1 ist" und "Nehmen Sie eine GCD für alle A und prüfen Sie, ob es 1 ist". ist. Sie können den zweiten machen, ohne darüber nachzudenken, aber Sie müssen den ersten entwickeln.

Wenn Sie GCD für alle Paare nehmen, erhalten Sie "TLE". Überlegen Sie sich also einen anderen Ansatz. Wenn die GCD 1 ist, bedeutet dies, dass die Zahl, die ein Vielfaches von A ist, die einmal ausgegeben wurde, nicht ausgegeben wird. Überprüfen Sie sie daher. Zählen Sie insbesondere die Anzahl der Vorkommen von `A```-Elementen im` memo``` -Array, fügen Sie jedem Indexschritt memo``` hinzu und ` Nimm sum```.

Achten Sie danach auf den bedingten Zweig "paarweises Koprime", "setweises Koprime" und "nicht Koprime" und geben Sie die Antwort aus.