C++で無限数直線上のターゲットに到達するための最小移動回数を求める方法

問題の概要

無限に続く数直線(−∞ から +∞)上で、位置 0 からスタートして指定されたターゲットに到達することを考えます。i 回目の移動では、左または右にちょうど i ステップ進むことができます。このとき、ターゲットに到達するために必要な最小の移動回数を求めます。

例えば、ターゲットが 2 の場合、最小ステップ数は 3 になります。移動の流れは「0 → 1 → -1 → 2」となります。

解法のアプローチ

この問題を解くためには、以下の重要なポイントを押さえておく必要があります。

• ターゲットが負の数であっても、数直線は原点を中心に対称であるため、正の数として扱って問題ありません。
• 基本的な戦略は、一方向にできるだけ遠くまで進むことです。つまり、0 → 1 → 3(1+2) → 6(1+2+3) → … と進みます。

n 回目の移動の後にちょうどターゲットに到達していれば、その移動回数 n が答えとなります。

しかし、到達点がターゲットを超えてしまう場合は、超過分の差に着目します。i 回目のステップの向きを反転させると、合計は (合計 − 2i) になります。もし sum − 2i がターゲットと一致すれば、そこが答えです。

ここで、ターゲットとの差が偶数か奇数かが重要になります。

• 差が偶数の場合: n 回の移動で答えが確定します。
• 差が奇数の場合: さらに 1 ステップ追加します。合計に n+1 を加算して再度差を確認し、n+1 で一致しなければ、n+2 でもう 1 ステップ進めます。差が偶数になるまで繰り返します。

C++による実装例

#include<iostream>
#include<cmath>
using namespace std;
int minStepToTarget(int target) {
    target = abs(target);
    int sum = 0, min_step = 0;
    while (sum < target || (sum - target) % 2 != 0) {
        min_step++;
        sum += min_step;
    }
    return min_step;
}
int main() {
    int target = 11;
    cout << "Minimum step to reach the target is: " << minStepToTarget(target);
}

出力

Minimum step to reach the target is: 5

コードの解説

この実装では、まず abs 関数でターゲットを絶対値に変換します。その後、合計 sum がターゲット以上になり、かつ差が偶数になるという条件を満たすまで、ステップ数を 1 ずつ増やしながら合計に加算し続けます。この条件を満たした時点での min_step が最小移動回数となります。

例えば target = 11 の場合、1+2+3+4 = 10 では 11 に届かず、1+2+3+4+5 = 15 で差は 4(偶数)となるため、答えは 5 になります。計算量はステップ数がおよそ √target 程度で収まるため、非常に効率的です。