Savings [AtCoder Beginner Contest 206（Sponsored by Panasonic） B]

https://atcoder.jp/contests/abc206/tasks/abc206_b

解説

https://atcoder.jp/contests/abc206/submissions/23625300

この問題は実は1日目から順番にシミュレートすれば間に合う。
200点問題ではあるが、ちょっと計算量について考え始めると心配になったりするかもしれない。

なぜ間に合う？

1+2+3+...+nという等差数列の総和は、公式を適用するとn(n+1)/2である。
Nの最大値は10⁹であるが、n=10⁵を入れてみると既に最大値を超えてしまう。
ちょっとだけ詳しく書くと総和をN以上にするためには、単純に足し合わせても約sqrt(N)日くらいでNを上回るので、
これはシミュレーションしても問題ない上限である。

愚直にシミュレーションする

1+2+3+...というのをシミュレーションしていき、N以上となったら、その時の日付を答える。
注意点は特にないが、個人的には上限をsqrt(N)とかにするよりかは適当に間に合う上限を入れておいた方が事故が少ない。
正直、上限をあまり厳密に評価してないが、余裕があるなら遊びを持たせておくぐらいの保険を自分はいつもいれている。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    int tot = 0;
    rep(day, 1, 1010101) {
        tot += day;
        if (N <= tot) {
            cout << day << endl;
            return;
        }
    }
}