ABC198 C - Compass Walking - かんプリンの学習記録

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${1}$ 歩でちょうど距離 ${R}$ 歩けるとき，原点から ${(X,Y)}$ まで最短何歩で行けるか．

${1\leq R \leq 10^5\\ 0\leq X,Y\leq 10^5}$

解説

${D^2=X^2+Y^2}$ とします．

${K}$ 歩歩くとすると ${KR < D}$ なら到達できないことがわかりますが， ${KR \geq D}$ なら到達できるでしょうか？

到達できそうですが ${D < R}$ のときには注意が必要で，図に書いてみるとわかるように ${2}$ 歩かかります．

以上から， ${D < R}$ のとき ${2}$ 歩， ${D \geq R}$ のとき $K\geq \frac{D}{R}$ を満たす最小の ${K}$ が答え．

${K}$ を求めるのに， ${D}$ が小数のままなのは誤差が怖いので両辺2乗して $K^2\geq \frac{D^2}{R^2}$ を満たす最小の ${K}$ を求めます．これは二分探索などを用いると高速に求めることができます．解の上限や判定を適当に決めてしまうとオーバーフローするので注意．

二分探索の実装が面倒なら ${K}$ を ${1}$ からいい感じの上限まで全探索する．これもオーバーフローに注意．

雑な上限評価： ${\displaystyle\frac{D^2}{R^2}\leq\left\lceil\frac{D^2}{R^2}\right\rceil\leq K^2\leq \left(\left\lceil\frac{D}{R}\right\rceil +1\right)^2\leq 141423^2}$

提出プログラム

https://atcoder.jp/contests/abc198/submissions/21700151

感想

今回は小数にビビらずにいってもAC取れる．