An Angle of Regular Polygon

解説

正 $N$ 角形の内角の総和は $180(N-2)$ 度であり、$1$ つの内角の大きさは $\displaystyle \frac{180(N-2)}{N}$ となります。

よって、$\displaystyle a \leq \frac{180(x-2)}{x}$ を満たすような最小の $x$ を求めれば良いです。

しかし、一つ懸念点があります。それは $x$ の範囲がわからないということです。ということで、 $x$ の範囲を調べます。先ほどの式を変形すると

$\displaystyle a \leq \frac{180(x-2)}{x} \leftrightarrow ax \leq 180(x-2) \leftrightarrow 360 \leq (180-a)x$

となり、$x$ の係数が最も小さくなる $a = 179$ を代入したとしても条件を満たす $x$ は $360 \leq x$ であり、 $x \leq 360$ の範囲で $x_{min}$ が見つかることになります。

よって、$3 \leq x \leq 360$ の範囲で$\displaystyle a \leq \frac{180(x-2)}{x}$ を満たすような最小の $x$ を探せばよく、 これ以上の $x$ の値について調べる必要がないことがわかりました。

愚直に $x$ を一個一個調べても時間計算量は $O(x)$ ですが、$x \leq 360$ より余裕を持って間に合います。

余談

• $\displaystyle　\frac{180(x-2)}{x}$ は単調減少な関数なので、答えを見つける上で二分探索が使えます。時間計算量は $O(log(x))$ となり、本制約に対して過剰に高速化が出来ます。

• $360 \leq (180-a)x$ を満たすような最小の $x_{min}$ は、 $x$ が整数であるという条件よりこの式から $\displaystyle x_{min} = \lceil(\frac{360}{180-a})\rceil$ であることが分かります。 これを利用することで時間計算量を $O(1)$ にできます。

• 今回の問題において、小数を扱うことによるWAの発生を確認できませんでしたが、基本的にこのような問題で小数を扱うのはやめましょう。