[PYTHON] AtCoder 174 BCD

Problème B

point

• Le pouvoir était **. J'étais accro à essayer de calculer avec ^
• Si sqrt (x ** 2, y ** 2) est utilisé dans le calcul de la distance, une erreur fractionnaire peut se produire et le nombre égal peut ne pas être complètement satisfait à la limite du nombre égal. Au lieu de cela, ce qui suit est recommandé ――Ne faites pas un nombre égal, ajoutez un très petit eps à celui qui devrait sortir grand, ou soustrayez-le avec celui qui devrait sortir petit --Carrez les deux côtés pour éviter sqrt et résolvez avec un entier! !!

B.py

import math
N, D = list(map(int,input().split()))
cnt = 0
for i in range(N):
    x, y = list(map(int, input().split()))
    if (x**2)+(y**2) <= D**2:
        cnt+=1
        
print(cnt)

Problème C

Je ne connaissais ni l'algorithme ni l'implémentation, et c'était en lambeaux.

point

--La séquence de nombres de 7, 77, 777 est régulière comme a_i = a_i * 10 + 7

• À ce moment, c'est trop régulier (périodique) --Si a_i est divisé par K et mod_i est utilisé, la séquence a_i est multipliée par 10 dans le terme précédent et ajoutée 7, donc naturellement elle est multipliée par 10 et ajoutée par 7. => mod_i = (mod_i-1 * 10 + 7)% K
• Lorsqu'il est divisé par K, il est inférieur à K. --De ce qui précède, il circule trop entre 0 et K. ―― Cela signifie que si vous essayez d'arranger les 7 jusqu'au chiffre K, vous finirez certainement le tour quelque part! !!
• Autrement dit, vous pouvez répéter jusqu'au nombre de 7 chiffres K arrangés. «On juge qu'il n'est pas divisible s'il circule, donc je veux en garder trop dans la liste et détecter la circulation. ――Mais lorsque le nombre d'éléments est très grand, l'ajout est incroyablement lent! !! !! ――Vous pouvez donc répéter avec gourmandise jusqu'à K

C.py

K=int(input())
amari=0
for i in range(K):
    amari = (amari * 10 + 7)% K
    if amari == 0:
        print(i+1)
        break
    if i == (K-1):
        print(-1)

C_RE.py

K=int(input())
amari_list = []
amari = 7%K
if amari == 0:
    print(1)
    
amari_list.append(amari)
for i in range(1,K):
    amari = (amari * 10 + 7)% K
    if amari == 0:
        print(i+1)
        break
    if amari in amari_list:
        print(-1)
        break
    if i == (K-1):
        print(-1)
    else:
        amari_list.append(amari)

Problème D

point

• Imaginez l'état final. ――Lorsque vous dites que le blanc n'est pas bon à gauche du rouge, il ne doit pas y avoir de rouge (même s'il n'est pas à côté) à droite d'un certain blanc. --Il existe de nombreux états de ce type (WWWW, RWWW, RRWW ...), vous pouvez donc comparer le nombre d'opérations dans chacun des états possibles.

• Le nombre d'opérations dans chaque état est déterminé par la différence entre l'état actuel et l'état cible. ――Pour être honnête, vous devez changer le nombre de couleurs différentes. Cependant, si vous échangez le blanc et le rouge pour plus de commodité, vous pouvez obtenir deux changements de couleur en une seule opération.

• Si vous recréez l'écart pour chaque état, vous vous retrouverez avec une double boucle (O (n ^ 2)), alors considérez une autre méthode. --Si vous changez l'état un par un à partir de la gauche, il vous suffit de regarder la partie modifiée, il n'est donc pas nécessaire de boucler

• Non prouvé, mais AC avec une solution plus simple. --Dans l'état final, R est continu à partir de la gauche et W est continu à droite. ――Lorsque vous souhaitez y parvenir, il semble que le remplacement soit toujours plus efficace que le changement de couleur. --Dans l'exemple d'entrée 3, lorsque "WRWWRWRR" est donné, il est nécessaire de changer la couleur quatre fois. Ce sera au minimum 3 fois en insérant des échanges. --Lorsque vous souhaitez atteindre l'état final en échangeant simplement, le nombre d'échanges requis peut être calculé en comparant la partie continue de W dans l'état final avec cette partie dans l'état actuel et en comptant le nombre de R.

D.py

_ = input()
s = input()

R_num = s.count("R")
print(s[:R_num].count("W"))