AtCoder ABC177 A-D mit Python

AtCoder ABC177 Ich habe versucht, das A-D-Problem mit Python zu lösen.

Ich habe an AtCoder ABC177 teilgenommen, daher werde ich es als Aufzeichnung veröffentlichen.

Ein Problem

Takahashi trifft sich mit Aoki. Der Treffpunkt ist D Meter von Takahashis Haus entfernt und die Treffzeit ist T Minuten später. Herr Takahashi wird von nun an sein Haus verlassen und mit S Metern pro Minute direkt zum Treffpunkt gehen. Wirst du pünktlich zum Treffen sein?

Gedanken

Die maximale Entfernung, die Takahashi, der sich mit S Metern pro Minute bewegen kann, in T Minuten zurücklegen kann, beträgt S * T. Sie können diesen Wert mit D vergleichen. (Ich habe versehentlich 1WA für die Ungleichung erhalten ())

d, t, s = map(int, input().split())
if s*t >= d:
    print("Yes")
else:
    print("No")

B Problem

Es sind zwei Zeichenfolgen S und T angegeben. Schreiben Sie einige Buchstaben von S neu, so dass T eine Teilzeichenfolge von S ist. Zumindest wie viele Zeichen muss ich umschreiben?

Gedanken

Verschieben Sie von len (S)> = len (T) die Zeichenfolge T in S, und die Antwort ist der Wert, der durch Subtrahieren der maximalen Anzahl übereinstimmender Zeichen von len (T) erhalten wird.

s = input()
t = input()
sl = len(s)
tl = len(t)

cnt = 0
ans = 0

for i in range(sl-tl+1):
    for j in range(tl):
        if t[j] == s[i+j]:
            cnt += 1
    
    ans = max(cnt, ans)#ans:Maximale Anzahl übereinstimmender Zeichen
    cnt = 0

print(tl - ans)

C Problem

N ganze Zahlen A1,…, AN sind gegeben. Finden Sie die Summe von Ai × Aj für alle Paare (i, j), die 1 ≤ i <j ≤ N mit mod (10 ** 9 + 7) erfüllen.

Gedanken

Wenn Sie die for-Anweisung ehrlich verdoppeln, ist sie eher TLE als O (N ^ 2) ... Als ich es vorerst schrieb, fand ich Folgendes. Betrachten Sie die Zeit von ex.i = 1, 2, .... Sei sum = A1 + A2 + ... AN. Wenn i = 1 A1 x A2 + A1 x A3 + A1 x A4 + A1 ・ ・ A1 + A1 x AN = A1 x (sum - A1) Wenn i = 2 A2 x A3 + A2 x A4 + A2 x A5 + A ・ ・ A + A2 x AN = A2 x (sum - A1 - A2) Wenn dies der Fall ist, kann dies durch O (N) unterdrückt werden. Wenn Sie dies in Python implementieren,

n = int(input())
A = [0]+list(map(int, input().split()))
mod = 10**9 + 7
S = sum(A)
ans = 0

for i in range(1, n):
    ans += A[i]*(S-A[i])
    ans %= mod
    S -= A[i]

print(ans)

D Problem

Es gibt N Personen von 1 bis N. Sie erhalten M Informationen, dass "People Ai und People Bi Freunde sind". Die gleichen Informationen können mehrfach gegeben werden. Wenn X und Y Freunde sind und Y und Z Freunde sind, dann sind X und Z auch Freunde. Es gibt auch keine Freundschaften, die nicht aus M Informationen abgeleitet werden können. Der böse Takahashi versucht, diese N Menschen in mehrere Gruppen aufzuteilen und eine Situation zu schaffen, in der jeder "keine Freunde in derselben Gruppe" hat. Wie viele Gruppen sollte ich mindestens teilen?

Gedanken

Beantworten Sie einfach die maximale Anzahl von Elementen im Set mit UnionFindTree. Dies liegt daran, dass die größte Menge zerlegt werden kann und die Elemente der anderen Mengen jedem Element zugewiesen werden können. Sie können die Erklärung von UnionFindTree verstehen, indem Sie sich Katsuppas Video auf Youtube ansehen. Probleme mit der Zeichenfolge 'Freund' werden wahrscheinlich mit UnionFind () verwendet.

import sys
sys.setrecursionlimit(10 ** 9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+1)

    def find(self, x):#Suchen Sie nach übergeordneten Elementen
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])#Rekursiv
            return self.root[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        elif self.rank[x] > self.rank[y]:#Verbunden mit einem tiefen Baum
            self.root[x] += self.root[y]
            self.root[y] = x#Sei x das Elternteil von y

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def issame(self, x, y):#x,Bestimmen Sie, ob y dieselbe Menge ist
            return self.find(x) == self.find(y)

    
    def count(self, x):#Anzahl der Elemente
        return (-1)*self.root[self.find(x)]

n, m = map(int, input().split())
uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a, b)

ans = 0

for i in range(n):
    ans = max(ans, uf.count(i))

print(ans)