C++で数直線上の点Xに到達するための最小ジャンプ回数を求める方法

問題の概要

整数 X が与えられたとき、0 から出発して X に到達するために必要な最小のジャンプ回数を求めます。最初のジャンプの長さは 1 単位で、それ以降の各ジャンプは直前のジャンプよりちょうど 1 単位ずつ長くなります。また、各ジャンプでは左方向・右方向のどちらにも移動することが許されています。

例えば X = 8 の場合、答えは 4 となります。0 → -1 → 1 → 4 → 8 という経路で到達できるからです。

解法の考え方

この問題を注意深く観察すると、次の性質が成り立つことが分かります。

• 常に右方向にジャンプし続けた場合、n 回のジャンプ後の位置は p = 1 + 2 + 3 + … + n、つまり n(n+1)/2 となります。
• k 番目のジャンプを左方向に変更すると、位置はちょうど 2k だけ減少します。方向を反転させると移動量が偶数分だけ変わるのがポイントです。
• どのジャンプを左にし、どのジャンプを右にするかを適切に選べば、n 回のジャンプ後に到達できる位置は、-n(n+1)/2 から n(n+1)/2 の範囲内で、かつ n(n+1)/2 と同じ偶奇（パリティ）を持つすべての点となります。

したがって、n(n+1)/2 が X 以上であり、かつ n(n+1)/2 と X の差が偶数であるという条件を満たす最小の n を求めれば、それが答えになります。差が偶数であれば、いくつかのジャンプの向きを反転させることで、余分な距離を必ず調整できるためです。

サンプルコード

#include<iostream>
#include<cmath>
using namespace std;
inline int sumOneToN(int n) {
    return (n * (n + 1)) / 2;
}
int jumps(int n) {
    n = abs(n);
    int ans = 0;
    while (sumOneToN(ans) < n or (sumOneToN(ans) - n) & 1)
        ans++;
    return ans;
}
int main() {
    int n = 9;
    cout << "Number of jumps: " << jumps(n);
}

出力

Number of jumps: 5

コードの解説

関数 sumOneToN は 1 から n までの合計（三角数）を計算します。関数 jumps では、まず X の絶対値を取ります。数直線は原点に対して対称であるため、負の値でも同様に扱えるからです。その後、三角数が X 以上になり、かつその差が偶数になるまで ans を増やし続けます。この条件を満たした時点の ans が最小ジャンプ回数です。

例えば X = 9 の場合、4 回のジャンプで到達できる最大距離は 10 ですが、差が 1 と奇数のため条件を満たしません。5 回目では 15 となり、差が 6 と偶数になるため、答えは 5 となります。