ABC174
平方根は使いません
pythondef 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回目までに結論が出る
pythondef 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) % KQ: 「K番目までにたどり着くことはわかっているので「たどり着かなかったらループだと判断」でもよかったか」
Yes、下記でACすることを確認した
pythondef solve(K):
p = 7 % K
for i in range(K):
if p == 0:
return i + 1
p = (p * 10 + 7) % K
return -1言及されてたことに気づいた
なるほど、そういう解き方、面白い。
こういう筆算を考えた時、一の位ははてなが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
Related Pages
- →僕のatcoderの学び方(〜青)×past5o×atcoder失敗リスト×abc175e×ABC174F×abc172e×abc178f×arc106c×arc106×arc105c×arc105d×arc104c×arc107d×貪欲法×最小カットに帰着→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]