C++で偵察部隊の結成方法を数えるコードの書き方

要素数 n の配列 A と整数 d が与えられたとします。ドリームランド軍の規定では、偵察部隊はちょうど 2 名の兵士で構成しなければならず、さらに 2 人の身長差は d センチメートル以内でなければなりません。n 人の兵士の身長は配列 A に格納されており、同じ身長の兵士が複数いる場合もあります。この記事では、この n 人の兵士から偵察部隊を結成する方法が何通りあるかを求める問題を解説します。

たとえば、入力が A = [10, 20, 50, 60, 65]、d = 10 の場合、出力は 6 になります。これは (10, 20)、(20, 10)、(50, 60)、(60, 50)、(60, 65)、(65, 60) の 6 通りの部隊編成が可能であるためです。

解法のアプローチ

この問題は、すべてのペアを順番に調べるシンプルな二重ループで解くことができます。手順は以下のとおりです。

1. 答えを保持する変数 ans を 0 で初期化します。
2. 外側のループで添字 i を 1 から配列の末尾まで動かします。
3. 内側のループで添字 j を 0 から i - 1 まで動かし、ペア (A[i], A[j]) をすべて列挙します。
4. |A[i] - A[j]| ≤ d を満たすペアが見つかるたびに ans を 1 増やします。
5. 最後に ans × 2 を返します。「(a, b)」と「(b, a)」のように順序が異なる編成も別々にカウントするためです。

C++ 実装例

理解を深めるために、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int d){
   int ans = 0;
   for (int i = 1; i < A.size(); i++)
      for (int j = 0; j < i; j++)
         if (abs(A[i] - A[j]) <= d)
            ans++;
   return ans * 2;
}
int main(){
   vector<int> A = { 10, 20, 50, 60, 65 };
   int d = 10;
   cout << solve(A, d) << endl;
}

入力

{ 10, 20, 50, 60, 65 }, 10

出力

6

計算量について

このアルゴリズムはすべてのペアを調べるため、時間計算量は O(n²) となります。n が小さい場合は十分実用的ですが、n が大きいケースでは、あらかじめ配列をソートした上で二分探索や尺取り法(スライディングウィンドウ)を組み合わせることで、O(n log n) まで高速化できます。