けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 056 C - Go Home (4Q, 茶色, 200 点)

AtCoder AtCoder200点 ABC-C 茶色diff NoviSteps4Q 最大値と最小値の間はすべて作れることに着目する 連結性に着目する O(√N)まで考えれば十分 小さいところで帳尻を合わせる 見積り大事

少し考察が必要になる問題。結局隙間なく作れる。

問題概要

最初、黒板に 0 という数が書かれている。 i = 1, 2, \dots 秒後には、黒板に書かれた数 x を以下のいずれかに置き換えることができる。

x-i, x, x+i

黒板に書かれた数を X にできるのは最短で何秒後か？

制約

  • 1 \le X \le 10^{9}

考えたこと

最初、「ちょうどぴったり X にするのは難しそうだ」と悩んでしまった。しかし、手を動かしてみると、たとえば

  • 1 秒後には、0, 1 が作れる
  • 2 秒後には、0, 1, 2, 3 が作れる
  • 3 秒後には、0, 1, 2, 3, 4 ,5, 6 が作れる
  • ...

というように 0 から「毎回足してできる数」まで、1 刻みですべて作れることがわかる。一般に、次のことが言える。

t 秒後までには、 0, 1, 2, \dots, \displaystyle \frac{t(t+1)}{2} まですべて作れる

よって、問題は

\displaystyle \frac{t(t+1)}{2} \ge X

を満たす最小の t を求めることだ。これは、 t = 1, 2, \dots と順番に試して行って、はじめて t * (t + 1) / 2 >= X となる瞬間を捉えればよい。

\frac{t(t+1)}{2} \ge X の左辺は二次式なので、 t = O(\sqrt{X}) まで試せば十分なため、計算量は O(\sqrt{X}) となって間に合う。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long X;
    cin >> X;
    for (long long i = 1; i <= X; i++) {
        if (i * (i + 1) / 2 >= X) {
            cout << i << endl;
            return 0;
        }
    }
}