C++で同じ積を持つタプルの総数を数える方法

問題の概要

互いに異なる要素を含む整数配列が与えられたとします。このとき、積が等しくなるタプルの総数を求めるのが課題です。

タプル (a, b, c, d) は、a*b = c*d が成り立つ場合に有効とみなされます。具体的な例を見てみましょう。

入力例：

arr[]= {2,4,6,3}

出力：

8

説明： 条件を満たすタプルの総数は8個です。(2,6,3,4)、(2,6,4,3)、(6,2,3,4)、(6,2,4,3)、(3,4,2,6)、(4,3,2,6)、(3,4,6,2)、(4,3,6,2) のいずれも a*b = c*d を満たしています。

解決のためのアプローチ

この問題を効率的に解く鍵となるのは、ペアの積をハッシュマップ（連想配列）で管理するというアイデアです。

マップを利用することで、同じ積を持つペア同士を簡単にグループ化でき、集計作業が大幅にシンプルになります。

まず、与えられた配列内のあらゆる要素の組み合わせについて積を計算し、マップを作成します。その後、マップを走査しながら、(a*b = c*d) の形で同じ積を持つペアがいくつ存在するかを確認していきます。

ここで重要なのは個数の計算方法です。ペアの総数は n*(n-1)/2 で求められ、さらに1つのペアには最大で 4*2 = 8 通りの並べ替え（順列）が存在します。したがって、各積に対して n*(n-1)/2*8 個のタプルが考えられることになります。

アルゴリズムの手順

• 配列の要素を入力として受け取ります。

• 整数関数 countTuples(int *arr, int n) が配列とそのサイズを受け取り、(a*b = c*d) を満たすタプルの数を返します。

• キーを「ペアの積」、値を「その積を持つペアの出現回数」とするハッシュマップを作成します。

• マップを反復処理し、同じ積を持つタプルの総数をカウントして返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int countTuple(int *arr, int n) {
   map<int, int> mp;
   for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++)
         mp[arr[i] * arr[j]]++;
   int ans = 0;
   for (auto it : mp)
      ans += (it.second * (it.second - 1) / 2) * 8;
   return ans;
}
int main(){
   int n=4;
   int arr[n]= {2,4,6,3};
   int res= countTuple(arr,n);
   cout<<res<<" ";
   return 0;
}

実行結果

8

このコードでは、まず二重ループですべてのペアの積をマップに記録し、次に各積ごとの出現回数から組み合わせの数 C(m, 2) を求め、順列の8倍を掛けて合計しています。

計算量について

時間計算量はペアの生成に O(n²)、マップの操作に平均 O(log n) かかるため、全体として O(n² log n) となります。空間計算量も保存するペアの数に依存し、最悪で O(n²) です。要素数が数百程度であれば十分に高速に動作します。