[PYTHON] AtCoder 174 BCD

B problem

point

--The power was **. I was addicted to trying to calculate with ^ --If you use sqrt (x ** 2, y ** 2) in the calculation of the distance, there is a possibility that a decimal error will occur and the equal sign cannot be completely satisfied at the boundary of the equal sign. Instead, the following is recommended -Do not make it an equal sign, add a very small eps to the one that should come out big, or subtract it with the one that should come out small --Square both sides to avoid sqrt and solve with integers! !!

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

I didn't know the algorithm or implementation, and it was tattered.

point

--The sequence of 7, 77, 777 is regular as a_i = a_i * 10 + 7 --At this time, it is too regular (periodic) --If a_i is divided by K and mod_i is used, the sequence a_i multiplies the previous term by 10 and adds 7, so naturally it is calculated by multiplying the previous term by 10 and adds 7. => mod_i = (mod_i-1 * 10 + 7)% K --When divided by K, it is less than K. --From the above, it circulates between 0 and K too much. ――This means that if you try the case of arranging 7s up to the K digit, you will definitely finish the round somewhere! !! --That is, repeat up to the number of K-digit 7s arranged. ――It is judged that it is not divisible if it circulates, so I want to keep too much in the list and detect the circulation. ――However, append is extremely slow when the number of elements is very large! !! !! ――So you can greedily repeat up to 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)

D problem

point

--Imagine the final state. ――When white is not good to the left of red, there must be no red (even if not next to it) to the right of a certain white. --There are many such states (WWWW, RWWW, RRWW ...), so you can compare the number of operations in each of the possible states. --The number of operations in each state is determined by the difference between the current state and the target state. ――To be honest, you need to change the number of different colors. However, if you exchange white and red for convenience, you can achieve two color changes with one operation. --If you re-create the gap for each state, you will end up with a double loop (O (n ^ 2)), so consider another method. --If you change the state one by one from the left, you only have to look at the changed part, so there is no need to loop.

--Unproven, but AC with a simpler solution. --In the final state, R is continuous from the left and W is continuous on the right. ――When you want to achieve this, it seems that replacement is always more efficient than changing colors. --In input example 3, when "WRWWRWRR" is given, it is necessary to change the color four times. It will be a minimum of 3 times by inserting exchanges. --When you want to achieve the final state by just exchanging, the number of exchanges required can be calculated by comparing the continuous part of W in the final state with that part in the current state and counting the number of R.

D.py

_ = input()
s = input()

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