C++で左右交互にN回移動した後の最終位置を求める方法

この問題では、3つの整数 N、A、B が与えられます。座標 0 の地点に立っている人が、まず右へ A ステップ進み、次に左へ B ステップ戻るという動作を交互に繰り返します。目的は、N 回の移動を完了した後の人物の最終的な座標を求めて出力することです。

問題例

入力: N = 4, A = 3, B = 1

出力: 4

説明:

1回目の移動 → 右に3 (+3)
2回目の移動 → 左に1 (-1)
3回目の移動 → 右に3 (+3)
4回目の移動 → 左に1 (-1)

4回移動後の位置 = +3 - 1 + 3 - 1 = 4

解き方の考え方

この問題を解くには、右方向の移動を正・左方向の移動を負として扱い、合計移動量を計算します。ここで重要なのは、奇数回目の移動は必ず右方向、偶数回目の移動は必ず左方向に行われるという規則性です。

つまり、N 回の移動のうち右方向への移動は (N+1)/2 回、左方向への移動は N/2 回発生します(整数除算・小数点以下切り捨て)。したがって、最終的な移動量は次の式で一発的に求められます。

Steps = ((n + 1) / 2) * a - (n / 2) * b

この式を使えば、実際に1回ずつ移動をシミュレーションする必要がなく、O(1) の計算量で答えを導き出せます。

C++による実装例

上記の解法を実装したプログラムは以下の通りです。

#include <iostream>
using namespace std;

void finalPosition(int n, int a, int b) {
    int steps = {((n + 1) / 2) * a - (n / 2) * b};
    cout << steps;
}

int main() {
    int N = 4, A = 3, B = 1;
    cout << "The final position of the person after " << N << " steps is ";
    finalPosition(N, A, B);
    return 0;
}

実行結果

The final position of the person after 4 steps is 4

まとめ

移動の交互パターンに着目して数式化することで、ループ処理なしに最終位置を効率的に計算できます。N が偶数・奇数のどちらの場合でも、整数除算の切り捨て特性によりこの式は正しく機能するため、シンプルかつ堅牢な実装になります。