ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC056 C - Go Home

問題
提出コード
ジャンプする時刻の最大値をkとすると、kから順番に1ずつ減らしてみていき(今見ている時刻をi とします)、Xよりiが小さければ時刻がiのときにジャンプすることにしてXからiを引く、という操作を繰り返していけば、ジャンプする時刻を求めることができます。これを繰り返してX=0になれば、ジャンプする時刻の最大値がkのときに、カンガルーは家に行くことができます。
結局は、1~kの総和がX以上になるようなkの最小値が答えになります。
1~kの総和は、\frac{k(k+1)}{2}で求めることができるので、k=1から大きく指定って調べれば、だいたいO(\sqrt{X})で答えを求めることができます。