C++で形成可能なチーム数を数えるアルゴリズム

n人の兵士が一列に並んでおり、それぞれの兵士には固有の評価値（rating）が割り当てられているとします。この中から、以下のルールに従って3人の兵士で構成されるチームを作ります。

インデックス (i, j, k) の3人の兵士を選び、その評価値が (rating[i], rating[j], rating[k]) であるとします。

チームが有効とみなされる条件は次のいずれかです。

• (rating[i] < rating[j] < rating[k]) — 評価値が昇順に並ぶ場合
• (rating[i] > rating[j] > rating[k]) — 評価値が降順に並ぶ場合

このとき、 formationできる有効なチームの総数を求めます（1人の兵士は複数のチームに所属できます）。

例えば、入力が rating = [2,5,3,4,1] の場合、(2,3,4)、(5,4,1)、(5,3,1) の3つのチームが作れるため、出力は 3 となります。

解法のアプローチ

この問題は、考えられるすべての組み合わせ (i, j, k) を三重ループで調べる全探索によって解くことができます。手順は以下の通りです。

• 答えを格納する変数 ret := 0、配列サイズ n := v.size() で初期化します。
• i を 0 から n-1 まで、j を i+1 から n-1 まで、k を j+1 から n-1 まで繰り返します。
• v[i] < v[j] かつ v[j] < v[k]（昇順）の場合、ret を1増やします。
• そうでなく、v[i] > v[j] かつ v[j] > v[k]（降順）の場合も、ret を1増やします。
• すべての組み合わせを確認したら、ret を返します。

実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numTeams(vector<int>& v) {
      int ret = 0;
      int n = v.size();
      for (int i = 0; i < n; i++) {
         for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
               if (v[i] < v[j] && v[j] < v[k])
                  ret++;
               else if (v[i] > v[j] && v[j] > v[k])
                  ret++;
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,5,3,4,1};
   cout << (ob.numTeams(v));
}

入力

{2,5,3,4,1}

出力

3

計算量について

この手法では3つのインデックスのすべての組み合わせを調べるため、時間計算量は O(n³)、空間計算量は O(1) となります。兵士の数 n が小さい場合は十分実用的ですが、n が大きくなる場合は、中央の要素 j ごとに「左側で自分より小さい・大きい要素の数」を数えることで O(n²) に改善する方法もあります。