C++で配列内の等差数列（AP）部分列の個数を数える方法

整数要素を含む配列 arr[] が与えられたとき、その中に存在する等差数列（Arithmetic Progression、AP）の部分列がいくつあるかを数えるのが本記事の目的です。配列内の要素の範囲は [1, 1000000] とします。

なお、空の部分列や要素が1つだけの部分列も等差数列としてカウントします。

例で理解する

例1

入力: arr[] = {1, 2, 3}

出力: 配列内のAP（等差数列）部分列の個数: 8

説明: 次の部分列が等差数列となります。

{}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}

例2

入力: arr[] = {2, 4, 5, 8}

出力: 配列内のAP（等差数列）部分列の個数: 12

説明: 次の部分列が等差数列となります。

{}, {2}, {4}, {5}, {8}, {2,4}, {2,5}, {2,8}, {4,5}, {4,8}, {5,8}, {2,5,8}

アルゴリズムの考え方

• 空の部分列も等差数列として扱います。
• 要素が1つの部分列も等差数列として扱います。
• 配列内の最小値と最大値を求めます。すべてのAP部分列の公差は、[最小値 − 最大値, 最大値 − 最小値] の範囲に必ず収まります。
• 各公差について動的計画法（DP）で部分列の個数を求め、arr_2[size] に格納します。
• 長さ2以上のAP部分列の総数は、各公差 D ごとの Σ(arr_2[i] − 1) の合計で求められます。
• 遷移式は arr_2[i] = 1 + Σ arr_2[j]（j < i かつ arr[j] + D = arr[i]）です。
• 高速化のため、「arr[j] + D = arr[i] かつ j < i」を満たす arr_2[j] の累積和を arr_3[max_size] に保持します。

実装の手順

• 整数配列 arr[] を入力として受け取ります。
• 関数 AP_subsequence(int arr[], int size) は、入力配列を受け取り、配列内のAP部分列の個数を返します。
• カウント用変数 count を 0 で初期化します。
• 変数 max_val、min_val、部分列数格納用の arr_2[size]、累積和格納用の arr_3[max_size] を用意します。
• forループで arr[] を走査して最大値・最小値を求めます。サンプルコードでは max_val を INT_MAX、min_val を INT_MIN で初期化しているため、走査後には max_val に最小値が、min_val に最大値が入ります（変数名と役割が逆になっていますが、以降の処理でも整合的に使われるため、最終的な結果は正しくなります）。
• 単一要素のAPと空のAPのぶんとして、count = size + 1 とします。
• 公差の下限 diff_max = max_val − min_val、上限 diff_min = min_val − max_val を計算し、i を diff_max から diff_min まで走査します。
• j = 0 から j < size まで forループで走査します。
• arr_2[j] = 1 と設定します。
• arr[j] − i が 1 以上 1000000 以下の場合、arr_2[j] += arr_3[arr[j] − i] とします。
• count に arr_2[j] − 1 を加算します。
• arr_3[arr[j]] = arr_3[arr[j]] + arr_2[j] として累積和を更新します。
• 最後に count を結果として返します。

C++での実装例

#include<bits/stdc++.h>

using namespace std;
#define max_size 10000

int AP_subsequence(int arr[], int size) {
    int count = 0;
    int max_val = INT_MAX;
    int min_val = INT_MIN;
    int arr_2[size];
    int arr_3[max_size];

    for (int i = 0; i < size; i++) {
        max_val = min(max_val, arr[i]);
        min_val = max(min_val, arr[i]);
    }
    count = size + 1;
    int diff_max = max_val - min_val;
    int diff_min = min_val - max_val;
    for (int i = diff_max; i <= diff_min; i++) {
        memset(arr_3, 0, sizeof arr_3);
        for (int j = 0; j < size; j++) {
            arr_2[j] = 1;
            if (arr[j] - i >= 1) {
                if (arr[j] - i <= 1000000) {
                    arr_2[j] += arr_3[arr[j] - i];
                }
            }
            count += arr_2[j] - 1;
            arr_3[arr[j]] = arr_3[arr[j]] + arr_2[j];
        }
    }
    return count;
}
int main() {
    int arr[] = {1,1,6,7,8};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of AP (Arithmetic Progression) Subsequences in an array are: " << AP_subsequence(arr, size);
    return 0;
}

上記のコードを実行すると、次の出力が得られます。

出力

Count of AP (Arithmetic Progression) Subsequences in an array are: 17

まとめ

本手法では、あり得るすべての公差についてDPを回すため、計算量は O(N × D)（N は配列長、D は公差の範囲の広さ）となります。空列と単一要素のぶんを最初に count = size + 1 として加算しておき、長さ2以上のAP部分列を各公差ごとに集計することで、配列内のAP部分列全体の個数を正確に求められます。