Quiz
https://atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_b
Submit
https://atcoder.jp/contests/cf16-final-open/submissions/4513717
Note
- 難しい問題ではないけれど、editorialに二分探索が書かれていないのと、解説記事Blogも書かれていないので書いておく
解法
- n項までの和は n * (n+1) / 2
- それがN以上であれば、n項までで作れる
- nをどうやって見つける？二分探索
- N以上になるn
- N以上を作れないn
- この境界を探す
- nが見つかれば、大きい方から使っていけばNを作れる
計算量（おまけ）
- N個の候補からnを見つける計算量はlog(N)
- n * (n+1) / 2 = Nなのでn = sqrt(N)ほど
- 長さnのforをする箇所で計算量はsqrt(N)
- よって合計は log(N) + sqrt(N)
- グラフ上でlog(x)とsqrt(x)ではsqrt(x)が上にくるので、O(sqrt(N))
