AtCoder Beginner Contest 174 - AtCoder
- 平方根は使いません python
def main():
N, D = map(int, input().split())
count = 0
for _i in range(N):
X, Y = map(int, input().split())
if X * X + Y * Y <= D * D:
count += 1
print(count)
- 高々10^6なので順番に見ていけばいいだけなのだけど、到達しないケースがあるのが問題
- 訪問済みの剰余をマークして真面目にループ検出した
- たどり着けるならK回目までにたどり着くので「K回目までにたどり着かなかったら到達不能と判断」でもよかったか
- Twitterを見てると「なぜ剰余？」的な意見があったので少し補足
- この数列は「前の数を10倍して7を足す」という操作を繰り返したもの
- 「Kの倍数」とは「Kで割ったあまりが0である数」
- 前の数の余りから次の数の余りがわかる
- 数列の各項を具体的に作らなくても、その余りだけわかればよい
- 大きな数を直接扱わなくてよい
- 余りが0になったらそれが探してた「Kの倍数」
- 余り0の数がみつかる前に、一度見た余りがまた出てきた場合、そこから先は同じことの繰り返しなので永遠に0に到達しない
- 余りはK通りしかないので、K回目までに結論が出る python
def solve(K):
visited = [False] * K
p = 7 % K
for i in range(K):
if p == 0:
return i + 1
if visited[p]:
return -1
visited[p] = True
p = (p * 10 + 7) % K
- Q: 「K番目までにたどり着くことはわかっているので「たどり着かなかったらループだと判断」でもよかったか」
- Yes、下記でACすることを確認した python
def solve(K):
p = 7 % K
for i in range(K):
if p == 0:
return i + 1
p = (p * 10 + 7) % K
return -1
-
言及されてたことに気づいた
- http://vvvvvv.sakura.ne.jp/ds14050/diary/20200803.html
- なるほど、そういう解き方、面白い。
- こういう筆算を考えた時、一の位ははてなが1個なので7に確定し、K X1の一の位が7になるX1も存在するなら一通りになる
- X1が確定すると上1行が確定するので、次は2行目について「10の位ははてなが1個だから確定する」となる
- このアルゴリズムが停止するのかどうかを考えてて気づいた
- 「余りの列はK番目までに0になるか、循環するかどちらか」の「循環する」に別の表現ができる
- 7がn個続いた数Aと、もっとたくさん続いた数BとでKでの余りが同じ場合、B-AはKの倍数
- B-Aは、Bより小さな7が続く数に10^nを掛けた数なので「Bまでに余り0が見つかってない」という条件から、Kは10^nの約数
- Kが1の時を除いてKの下一桁が偶数か5になる
- このアルゴリズムでは「掛け算結果の下一桁が7にならない」ので速やかに停止してる
- そこで停止しなかったものに関しては短いループに入らないことが保証されているので、K回目までに解にたどりつく
-
ABC174D AC
-
ABC174E AC after contest
