ABC206B - Savings

B - Savings

考えたこと

\begin{aligned}
\sum_{i=1}^{k} = \frac{k(k+1)}{2}
\end{aligned}
だから,
\begin{aligned}
\frac{k(k+1)}{2} \geq N
\end{aligned}
を満たす最小の正整数$k$を求めれば良い.

2次方程式

\begin{aligned}
& \frac{k(k+1)}{2} = N \\
&\Leftrightarrow k^{2} + k - 2N = 0
\end{aligned}
の解は
\begin{aligned}
k=\frac{-1\pm \sqrt{1 + 8N}}{2}
\end{aligned}
であるが,$k > 0$となるのは
\begin{aligned}
k=\frac{-1 + \sqrt{1 + 8N}}{2}
\end{aligned}
である.よって,$\lceil k \rceil=$math.ceil(k)が答え.

別解

Editorial - AtCoder Beginner Contest 206(Sponsored by Panasonic)
二分探索は覚えておきたい.