C++で[-k、+k]の範囲内にとどまる移動方向を出力する方法

この問題では、ユーザーから与えられた一定の範囲内にとどまるように、正方向または負方向への有効な移動手順を見つける必要があります。

具体的には、移動できる最大値を示す上限 K と、n 個の正の値からなる移動量の配列が与えられます。それぞれの移動量に対して正方向・負方向のどちらに進むべきかを判定し、位置が一度も上限 K を超えないような方向の列を出力することが求められます。

具体例を使って、このトピックをより深く理解していきましょう。

入力 : K = 56、配列 = [25, 14, 31, 16, 5]
出力 : positive positive negative positive positive

解説

まず、0 + a[0] = 0 + 25 = 25 < 56 であるかを確認します。条件を満たすので、正方向へ移動します。

次に、25 + a[1] = 25 + 14 = 39 < 56 であるかを確認します。これも条件を満たすので、正方向へ移動します。

続いて、39 + a[2] = 39 + 31 = 70 となり 56 を超えてしまうため、正方向には進めません。そこで 39 − a[2] = 39 − 31 = 8 > 0 であることを確認し、負方向へ移動します。

さらに、8 + a[3] = 8 + 16 = 24 < 56 なので、正方向へ移動します。

最後に、24 + a[4] = 24 + 5 = 29 < 56 なので、正方向へ移動します。

以上により、求める出力は「positive positive negative positive positive」となります。

解法の考え方

この問題を解くロジックはシンプルです。まず、正方向に移動しても上限に達しないかどうかを確認します。達しないのであれば正方向へ進みます。そうでない場合は、負方向に移動しても下限(0 または -K)を下回らないかを確認し、下回らなければ負方向へ進みます。両方とも不可能な場合は、有効な移動が存在しないものとして処理を終了します。

この考え方に基づいて、コードを作成する際に従うべきアルゴリズムは以下の通りです。

アルゴリズム

初期位置(position)を 0 に設定する。
Step 1 : i を 0 から n まで(n は配列の長さ)繰り返し、Step 2〜4 を実行する。
Step 2 : initial_position + a[i] <= K の場合、initial_position += a[i] とし、「POSITIVE」を出力する。
Step 3 : そうでなければ、initial_position - a[i] >= 0 の場合、initial_position -= a[i] とし、「NEGATIVE」を出力する。
Step 4 : いずれの条件も満たさない場合、「NO MORE VALID MOVES(有効な移動なし)」を出力する。

実装例

それでは、このアルゴリズムを実装して問題を解くプログラムを実際に作成してみましょう。

#include <iostream>
using namespace std;
void StepsTaken(int a[], int n, int k){
    string res = "";
    int position = 0;
    int steps = 1;
    for (int i = 0; i < n; i++) {
        if (position + a[i] <= k && position + a[i] >= (-k)) {
            position += a[i];
            cout<<"POSITIVE \t";
        }
        else if (position - a[i] >= -k && position - a[i] <= k) {
            position -= a[i];
            cout<<"NEGATIVE \t";
        } else {
            cout << -1;
            return;
        }
    }
    cout << res;
}
int main(){
    int a[] = { 12 , 24 , 9 , 17 , 8};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 40;
    StepsTaken(a, n, k);
    return 0;
}

出力

POSITIVE    POSITIVE    NEGATIVE    NEGATIVE    POSITIVE