AtCoder 174 BCD

B問題

ポイント

• 累乗は**でした。^で計算しようとしてハマった
• 距離の計算でsqrt(x2, y2)とすると小数誤差が生じて等号の境界でぴたりと等号を満たせない可能性がある。代わりに以下が推奨
  • 等号にせず、ごく小さいepsを大きく出るべき方に足すか小さく出るべき方で引く
  • 両辺を二乗してsqrtを避け、整数で解く！！

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問題

アルゴリズムも実装もわからずボロボロでした。

ポイント

• 7, 77, 777の数列はa_i = a_i*10 + 7 と規則的
• このとき、あまりも規則的（周期的）
  • a_i をKでわったあまりをmod_iとすると、数列a_iは前項を10倍して7を足すので、当然前項に対して計算したあまりも10倍して7を足す。 => mod_i = (mod_i-1 * 10 + 7) % K
• Kで割った時のあまりはK以下。
• 上記より、あまりは0~Kの間で循環する。
  • これは、K桁まで7を並べるケースを試せば、必ずどこかで一巡を終えるということ！！
  • すなわちK桁の7を並べた数まで繰り返せばいい
• 循環すれば割り切れないと判断なので、あまりをリストで保持して循環を検知したい。
  • しかし、要素数が非常に大きいときのappendはめちゃくちゃ遅い！！！
  • なので貪欲に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問題

ポイント

• 最終状態をイメージする。

• 赤の左に白がだめ、というとき、ある白の右には（隣でなくとも）赤があってはいけない。

• そのような状態はいくつもある(WWWW, RWWW, RRWW...) ので、その起こりえる状態のなかでそれぞれ操作回数を比較すればよい

• 各状態の操作回数は現在の状態と目標の状態の差で決まる。

  • 愚直に行えば、色が異なる数だけ色変えをする必要がある。しかし、都合のよい白と赤を交換すれば色変え2回分を一度の操作で達成できる。
  • 状態毎にギャップを図り直すと2重ループ（O(n^2)）になってしまうので、他の方法を考える。
    • 状態を左からひとつずつ変えれば、その変えた部分だけ見ればよいのでループする必要がなくなる

• 未証明だが、より簡潔な解法でACした。

• 最終状態は左からRが連続し、右にはWが連続する状態になる。

• これを達成したいとき、色変えよりも交換の方が常に効率的っぽい

  • 入力例3で、「WRWWRWRR」が与えられたとき、色変えだけでは4回必要。交換を入れることで最小の3回になる。

• 交換だけでこれを最終状態を実現したいとき、必要な交換の回数は、最終状態のWの連続部分と現状のその部分を比較して、Rの数を数えればよい

D.py

_ = input()
s = input()

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