[Codeforces] Educational Codeforces Round 99 (Div. 2) B. Jumps

2020年12月13日

問題

方針

\( t \) 回のジャンプで行くことができる最大の点は

\[\dfrac{t(t + 1)}{2}\]

となります。ここで、自然数 \( t \) を

\[ \dfrac{t(t + 1)}{2} \geq x\]

を満たす最小の \( t \) とします。このとき今いる座標がちょうど \( x \) となれば答えは \( t \) となります。以降は、

\[ \dfrac{t(t + 1)}{2} > x\]

の場合を考えます。ここで、\( t \) 回のジャンプのどれかで \( 1 \) 戻るジャンプに入れ替えることを考えます。\( v \) 回目のジャンプを入れ替えるとすると、座標は

\[ \dfrac{t(t + 1)}{2} – v – 1\]

となります。したがって、

\begin{eqnarray}
\dfrac{t(t + 1)}{2} – v – 1 &=& x\\
v &=& \dfrac{t(t + 1) – 2x – 2}{2}
\end{eqnarray}

となります。したがって、\( v \geq 1 \) ならば、答えは \( t \) となります。ここで、\( t(t + 1) \) は \( 2 \) の倍数なので、

\[ t(t + 1) – 2x – 2 = 0 \]

のときを考えます。このとき、

\[ \dfrac{t(t + 1)}{2} – x = 1\]

なので、\( 1 \) 戻るジャンプを新たにすれば、\( x \) に到達するので答えは \( t + 1 \) となります。

また、\( t \) 回のジャンプの中で \( 2 \) つのジャンプを \( 1 \) 戻るジャンプに入れ替えることを考えると、

\[ \dfrac{t(t + 1)}{2} – (v + 1) – (w + 1) = x\]

という方程式を考えることになりますが、\( z = v + w \) と置き換えて考えると、無駄な操作であることが分かります。

コード

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

int bs(int x) {
    int l = 0;
    int r = 10000;
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        if ((m * (m + 1)) / 2 >= x) {
            r = m;
        } else {
            l = m;
        }
    }
    return r;
}
int main() {
    int t, x;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> x;
        int t = bs(x);
        int e = t * (t + 1) - 2 * x - 2;
        if (t * (t + 1) == 2 * x || (e / 2 >= 1)) {
            cout << t << "\n";
        } else {
            cout << t + 1 << "\n";
        }
    }
    return 0;
}