C++で数直線上の目標位置に到達するための最小移動回数を求める

無限に続く数直線上の位置0に立っているとします。目標地点は位置 target にあります。各移動では、左方向または右方向のどちらにも進むことができ、n回目の移動(1から開始)ではちょうどn歩進むことになります。このとき、目的地に到達するために必要な最小の移動回数を求めるのが課題です。

例えば、target = 3 の場合、答えは 2回 となります。0から1へ(+1)、1から3へ(+2)と進むことで、ちょうど2回の移動で目標に到達できます。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• target := |target|、cnt := 0 と初期化する
• target > 0 の間、以下を繰り返す:
  • cnt を1増やす
  • target := target − cnt
• ループ終了後、target(= 超過分)が偶数なら cnt を返し、そうでなければ cnt + 1 + (cnt mod 2) を返す

なぜこの方法でうまくいくのか

まず、1 + 2 + 3 + … と移動距離を加算していき、合計が初めて target 以上になった時点での回数を cnt とします。このときの超過分(target を引いた残り)が偶数であれば、途中のいくつかの移動の向きを反転させることで、総和を変えずにちょうど target に到達できます。

一方、超過分が奇数の場合は、向きの反転だけでは偶奇が変わらないため、追加の移動が必要になります。cnt が偶数なら1回、奇数なら2回の追加移動で偶奇が反転し、必ず到達できることが証明されています。式 cnt + 1 + cnt % 2 はこの調整をまとめて表したものです。

C++による実装例

それでは、理解を深めるために実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int reachNumber(int target) {
        target = abs(target);
        int cnt = 0;
        while(target > 0){
            target -= ++cnt;
        }
        return target % 2 == 0? cnt : cnt + 1 + cnt % 2;
    }
};
main(){
    Solution ob;
    cout << (ob.reachNumber(3));
}

入力

3

出力

2

このアルゴリズムの計算量は O(√target) であり、1からcntまでの和が target を超えるまでループするだけなので、非常に効率的に動作します。負の target も絶対値を取ることで対称的に処理できる点もポイントです。