[PYTHON] AtCoder 174 BCD

B-Problem

Punkt

• Die Macht war **. Ich war süchtig danach, mit ^ zu rechnen
• Wenn bei der Berechnung der Entfernung sqrt (x ** 2, y ** 2) verwendet wird, kann ein Bruchfehler auftreten und die gleiche Zahl kann an der Grenze der gleichen Zahl nicht vollständig erfüllt sein. Stattdessen wird Folgendes empfohlen ――Machen Sie es nicht zu einer gleichen Zahl, fügen Sie ein sehr kleines Eps zu dem hinzu, das groß herauskommen soll, oder subtrahieren Sie es mit demjenigen, das klein herauskommen soll
• Quadrieren Sie beide Seiten, um sqrt zu vermeiden und lösen Sie mit einer ganzen Zahl! !!

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)

C-Problem

Ich kannte den Algorithmus und die Implementierung nicht und es war zerfetzt.

Punkt

• Die Zahlenfolge von 7, 77, 777 ist regulär als a_i = a_i * 10 + 7
• Zu dieser Zeit ist es zu regelmäßig (periodisch) --Wenn a_i durch K geteilt wird und mod_i verwendet wird, wird die Folge a_i im vorherigen Term mit 10 multipliziert und mit 7 addiert, also natürlich mit 10 multipliziert und mit 7 addiert. => mod_i = (mod_i-1 * 10 + 7)% K.
• Wenn durch K geteilt, ist es weniger als K.
• Aus dem oben Gesagten zirkuliert es zu viel zwischen 0 und K. ――Dies bedeutet, dass Sie die Runde definitiv irgendwo beenden werden, wenn Sie versuchen, 7s bis zur K-Ziffer anzuordnen! !! --Das heißt, Sie können bis zu einer Anzahl von K-stelligen 7s wiederholen. ――Es wird beurteilt, dass es nicht teilbar ist, wenn es zirkuliert, deshalb möchte ich zu viel in der Liste behalten und die Zirkulation erkennen. ――Aber wenn die Anzahl der Elemente sehr groß ist, ist das Anhängen wahnsinnig langsam! !! !! ――So können Sie gierig bis zu K wiederholen

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)

D Problem

Punkt

• Stellen Sie sich den Endzustand vor. ――Wenn Sie sagen, dass Weiß links von Rot nicht gut ist, darf rechts von einem bestimmten Weiß kein Rot (auch nicht daneben) stehen.

• Es gibt viele solcher Zustände (WWWW, RWWW, RRWW ...), sodass Sie die Anzahl der Operationen in jedem der möglichen Zustände vergleichen können.

• Die Anzahl der Operationen in jedem Zustand wird durch die Differenz zwischen dem aktuellen Zustand und dem Zielzustand bestimmt. ――Um ehrlich zu sein, müssen Sie die Anzahl der verschiedenen Farben ändern. Wenn Sie jedoch der Einfachheit halber Weiß und Rot austauschen, können Sie mit einem Vorgang zwei Farbänderungen erzielen.

• Wenn Sie die Lücke für jeden Zustand neu erstellen, erhalten Sie eine Doppelschleife (O (n ^ 2)). Ziehen Sie also eine andere Methode in Betracht.

• Wenn Sie den Status einzeln von links ändern, müssen Sie nur den geänderten Teil betrachten, sodass keine Schleife erforderlich ist

• Nicht bewiesen, aber AC mit einer einfacheren Lösung.

• Im Endzustand ist R von links durchgehend und W von rechts durchgehend. ――Wenn Sie dies erreichen möchten, scheint der Austausch immer effizienter zu sein als das Ändern der Farben.

• Wenn in Eingabebeispiel 3 "WRWWRWRR" angegeben ist, muss die Farbe viermal geändert werden. Es wird mindestens dreimal durch Einfügen von Börsen erfolgen.

• Wenn Sie den Endzustand durch einfaches Austauschen erreichen möchten, können Sie die Anzahl der erforderlichen Austausche berechnen, indem Sie den kontinuierlichen Teil von W im Endzustand mit dem Teil im aktuellen Zustand vergleichen und die Anzahl von R zählen.

D.py

_ = input()
s = input()

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