C++プログラムで偵察ユニットを編成できる兵士のペア（インデックス）を見つける方法

問題概要

n個の要素を持つ配列Aがあり、n人の兵士が円形に並んでいるとします。i番目の兵士の身長はA[i]で表されます。偵察ユニットは、隣り合う2人の兵士のうち、身長差が最も小さいペアで編成されます。身長の近い2人が並ぶことで、お互いに目立ちにくくなるためです。この記事では、偵察ユニットを編成できる兵士のペアのインデックスを求めるC++プログラムを紹介します。

例えば、入力が A = [10, 12, 13, 15, 10] の場合、出力は (5, 1) となります。これは、5番目の兵士（身長10）と1番目の兵士（身長10）が円の上で隣り合っており、身長差が0と最小であるためです。

解法のステップ

兵士は円形に並んでいるため、最初の兵士と最後の兵士も隣り合っている点に注意が必要です。以下の手順に従うことで、最適なペアを見つけられます。

1. n を配列Aのサイズとします。
2. D を、最初と最後の兵士の身長差 |A[0] − A[n−1]| で初期化します。
3. H を n で初期化します。
4. i を 1 から n−1 まで繰り返します。もし D > |A[i] − A[i−1]| であれば、D を |A[i] − A[i−1]| に、H を i に更新します。
5. 最後に H と (H mod n) + 1 を出力します。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> A) {
    int n = A.size();
    int D = abs(A[0] - A[n - 1]);
    int H = n;
    for (int i = 1; i < n; i++) {
        if (D > abs(A[i] - A[i - 1])) {
            D = abs(A[i] - A[i - 1]);
            H = i;
        }
    }
    cout << H << ", " << (H % n) + 1;
}
int main() {
    vector<int> A = { 10, 12, 13, 15, 10 };
    solve(A);
}

入力

{ 10, 12, 13, 15, 10 }

出力

5, 1

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量はO(n)、追加の記憶領域はO(1)と非常に効率的です。兵士の人数が多くなっても高速に動作するのが特徴です。