Pythonで数の2乗が2つの数の積と等しくなるトリプレットの総数を求める方法

問題の概要

2つの整数配列 nums1 と nums2 が与えられたとき、次の2つのルールを満たすトリプレット (i, j, k) の総数を求めることを考えます。

• 型1： nums1[i]^2 = nums2[j] × nums2[k] を満たすトリプレット。ただし 0 ≤ i < len(nums1)、かつ 0 ≤ j < k < len(nums2)
• 型2： nums2[i]^2 = nums1[j] × nums1[k] を満たすトリプレット。ただし 0 ≤ i < len(nums2)、かつ 0 ≤ j < k < len(nums1)

例として、nums1 = [7, 4]、nums2 = [5, 2, 8, 9] の場合を考えてみましょう。このとき答えは 1 になります。型1のトリプレット (1, 1, 2) において、nums1[1]^2 = nums2[1] × nums2[2]、すなわち 16 = 2 × 8 が成り立つためです。型2を満たす組み合わせは存在しないため、合計は 1 となります。

解法の考え方

すべてのインデックスの組み合わせを素朴に調べると計算量が膨大になります。そこで collections.Counter を使って各値の出現回数を事前に記録しておくことで、数え上げを大幅に効率化できます。

アルゴリズムの手順

• cnt1：nums1 の各要素とその出現回数を保持するマップ（Counter）
• cnt2：nums2 の各要素とその出現回数を保持するマップ（Counter）
• 関数 triplets(arr1, arr2) を定義する
• ans = 0 で初期化
• arr1 の各要素 t とその出現回数 v について以下を処理する：
  • k ＝ arr2 における t の出現回数（存在しない場合は 0）。同じ値 t を2つ選ぶ組み合わせは C(k, 2) 通りなので、tmp = k * (k - 1) // 2
  • sq ＝ t の2乗
  • arr2 の各要素 m に対して、「m < t かつ sq が m で割り切れる」場合、tmp に arr2[m] × arr2[sq ÷ m] を加算する（キーが存在しない場合は 0 として扱う）
  • ans += tmp * v
• ans を返す
• 最終的な答えは triplets(cnt1, cnt2) + triplets(cnt2, cnt1) となる

Pythonでの実装例

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

from collections import Counter


def solve(nums1, nums2):
    cnt1 = Counter(nums1)
    cnt2 = Counter(nums2)

    def triplets(arr1, arr2):
        ans = 0
        for t, v in arr1.items():
            # 相手側に同じ値 t が k 個あれば、その中から2つ選ぶ組み合わせは C(k, 2)
            k = arr2.get(t, 0)
            tmp = k * (k - 1) // 2
            sq = t * t
            # m < t かつ sq が m で割り切れ、商も相手側に存在する場合を加算
            for m in arr2:
                if m < t and sq % m == 0:
                    tmp += arr2.get(m, 0) * arr2.get(sq // m, 0)
            ans += tmp * v
        return ans

    return triplets(cnt1, cnt2) + triplets(cnt2, cnt1)


nums1 = [7, 4]
nums2 = [5, 2, 8, 9]
print(solve(nums1, nums2))

入力

[7, 4], [5, 2, 8, 9]

出力

1

処理の流れと計算量

上の例では、t = 4 のとき sq = 16 となり、m = 2 が条件（m < t かつ 16 % 2 == 0）を満たします。さらに商の 16 ÷ 2 = 8 も nums2 に存在するため、tmp に 1 × 1 = 1 が加算されます。これがトリプレット (1, 1, 2) に対応しており、結果として 1 が出力されます。

計算量について見てみると、重複を除いた各配列の要素数を D1、D2 とすると、全体の計算量は O(D1 × D2) に抑えられます。すべての組み合わせを調べる O(n³) の素朴な手法と比較して、はるかに高速に動作するのがこのアプローチの大きな利点です。