【C++】最初の3項が等差数列・最後の3項が等比数列になる4つ組の個数を求める方法

この記事では、最初の3項が等差数列（A.P.）、最後の3項が等比数列（G.P.）を満たす4つ組の個数を求めるためのさまざまなアプローチを詳しく解説します。まずは、等差数列と等比数列の基本的な定義から見ていきましょう。

等差数列（A.P.）とは

等差数列とは、隣り合う2つの項の差（公差 d）が常に一定である数列のことです。つまり、連続する2つの数の差が常に同じになります。
例：1, 3, 5, 7, 9（公差 d = 2）

等比数列（G.P.）とは

等比数列とは、隣り合う2つの項の比（公比 r）が常に一定である数列のことです。各項は、前の項に固定の数を掛けることで求められます。
例：3, 6, 12, 24, …（公比 r = 2）

問題の概要

この問題では、N個の整数からなる配列 arr[ ] について、条件を満たすインデックスの4つ組 (a, b, c, d) がいくつ存在するかを求めます。具体的には、arr[a]、arr[b]、arr[c] がこの順で等差数列をなし、arr[d]、arr[c]、arr[b] がこの順で等比数列をなす（＝arr[c]² = arr[b] × arr[d] が成り立つ）ような4つ組をすべて数えます。

以下に具体例を示します。

入力 : arr[ ] = { 9, 6, 4, 2, 1, 2 }
出力 : 2
説明 : 4つ組を構成する要素は { 3, 2, 1, 0 } と { 5, 2, 1, 0 } のインデックスにあり、いずれの場合も4つ組は { 2, 4, 6, 9 } となります。

入力 : arr[ ] = { 2, 6, 1, 4, 2 }
出力 : 2
説明 : 4つ組を構成する要素は { 1, 3, 0, 2 } と { 1, 3, 4, 2 } のインデックスにあり、いずれの場合も4つ組は { 6, 4, 2, 1 } となります。

解法のアプローチ

それでは、この問題を解くための2つのアプローチを順番に見ていきましょう。

1. 全探索（ブルートフォース）アプローチ

最もシンプルな方法は、4重のネストされたループですべての組み合わせを調べることです。まず最初の3つの要素が等差数列になっているかを確認し、なっていれば残りの3つの要素が等比数列になっているかをチェックします。条件を満たしていればカウント変数を1増やします。ただし、この方法は時間計算量が O(n⁴) となるため、非常に時間がかかるという欠点があります。

2. 効率的なアプローチ

このアプローチでは、まず各配列要素の出現回数をハッシュマップで記録します。そのうえで、第2要素と第3要素を固定して2重ループを実行します。このとき、第1要素は arr[b] − (arr[c] − arr[b])、第4要素は arr[c] × arr[c] ÷ arr[b] として求められるのがポイントです。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int main (){
    unordered_map<int, int> map;
    int arr[] = { 2, 6, 1, 4, 2 };
    int size = sizeof(arr) / sizeof(arr[0]);
    // すべての要素を処理し、出現回数をカウントアップ
    for (int a = 0; a < size; a++)
        map[arr[a]]++;

    int count = 0;
    // 第2要素と第3要素を決めるための2重ループ
    for (int b = 0; b < size; b++){
        for (int c = 0; c < size; c++){
            if (b == c)
                continue;
            // 使用中の要素分だけカウントを減らす
            map[arr[b]]--;
            map[arr[c]]--;
            // 公差を使って第1要素を求める
            int first = arr[b] - (arr[c] - arr[b]);
            // 等比数列の性質を使って第4要素を求める
            int fourth = (arr[c] * arr[c]) / arr[b];
            if ((arr[c] * arr[c]) % arr[b] == 0){
                // 第2要素と第3要素が異なる場合はそのままカウント
                if (arr[b] != arr[c])
                    count += map[first] * map[fourth];
                else
                    count += map[first] * (map[fourth] - 1);
            }
            map[arr[b]]++;
            map[arr[c]]++;
        }
    }
    cout << "Number of quadruples: " << count;
    return 0;
}

実行結果

Number of quadruples: 2

コードの解説

このコードでは、組み合わせ論の考え方を活用しています。第2要素（b）と第3要素（c）を固定した2重ループの中で、第1要素を arr[b] − (arr[c] − arr[b])、第4要素を arr[c] × arr[c] ÷ arr[b] として導出します。そして、第2・第3要素を固定した状態における4つ組の総数は、「第1要素となれる値の出現回数 × 第4要素となれる値の出現回数」として計算できます。このコードの時間計算量は O(n²) であり、全探索と比較して大幅に高速化されています。

まとめ

この記事では、最初の3項が等差数列（A.P.）、最後の3項が等比数列（G.P.）を満たす4つ組の個数を求める問題を取り上げました。全探索による手法（O(n⁴)）と、ハッシュマップを活用した効率的な手法（O(n²)）の2つのアプローチを紹介しました。

ここではC++で実装しましたが、同じロジックはJava、Python、Cなど、その他のプログラミング言語でも同様に実装できます。ぜひ自分の使い慣れた言語でも試してみてください。