AtCoder ABC 177 Python (A ~ E)

Résumé

Seuls A et D ont été résolus. Je suis resté coincé en B et je n'ai pas pu résoudre C ... Le seul salut était que D a été résolu immédiatement. Je n'ai pas pu avancer vers E en raison de la perte de temps de B et C. Ce fut un résultat décevant.

problème

AtCoder Beginner Contest 177

A. Don't be late

Répondre

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

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

Trouvez le temps temps``` lorsque vous voyagez D mètres à la vitesse` `` S et comparez-le avec la limite de temps `` T```.

B.Substring (AC à une date ultérieure)

Répondre

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)

La politique est

1. Essayez toutes les chaînes `` `S``` depuis le début
2. Jugez que l'indice `s``` sélectionné ci-dessus correspond à la chaîne de caractères` `T```
3. Comptez le nombre d'indices où S et `` T ne correspondent pas
4. Répétez les étapes 1 et 2 et prenez min``` pour répondre est.

J'ai trop réfléchi au moment du concours. L'exemple de réponse ci-dessus compte principalement S '', mais au moment du concours, j'ai essayé de compter principalement T '' et cela n'a pas fonctionné.

C. Somme du produit des paires (AC à une date ultérieure)

Répondre

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)

C'est facile si vous remarquez la transformation de formule suivante.

(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

La liste A est "au carré et additionnée" sous la forme `sq_sum```, et le" total et au carré "se trouve sous la forme` sum_sq```. Prenez la différence et divisez par 2.

D. Friends

Répondre

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 personnes, M relations
    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)
   

Le seul modèle `` Union Find '' que je préparais était utile. Afin de créer un groupe afin qu'il n'y ait pas d'amis dans le même groupe, il semble que les membres du groupe ayant la plus grande amitié devraient être séparés.

La politique est

1. Gérez les attributs de groupe avec Union Find
2. Vérifiez la taille de chaque groupe
3. La plus grande taille de groupe est la réponse

est.

E. Coprime

Réponse (AC à une date ultérieure)

import math
L = 10**6 + 1

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

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

for i in range(2, L): #Un pgcd de 1 en tout équivaut à aucun nombre dans l'étape pour chaque nombre d'intérêt
    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)

Il y a deux choses à faire: "prendre un GCD pour toutes les paires et vérifier s'il vaut 1" et "prendre un GCD pour tous les A et vérifier s'il vaut 1". est. Vous pouvez faire le second sans y penser, mais vous devez concevoir le premier.

Si vous prenez GCD avec toutes les paires, ce sera TLE '', alors envisagez une approche différente. Si le GCD est 1, cela signifie que le nombre qui est un multiple de A qui est sorti une fois ne sort pas, alors vérifiez-le. Plus précisément, comptez le nombre d'occurrences de l'élément ```A``` dans le tableau mémo```, ajoutez `mémo``` à chaque étape d'indice, et ajoutez le. Prenez `` somme ''.

Après cela, faites attention à la branche conditionnelle de "coprime par paires", "setwise coprime" et "pas coprime" et affichez la réponse.