C++でk^m（m≥0）の形の合計を持つ部分配列の個数を求める方法

はじめに

この記事では、C++を使って「合計がk^m（m ≥ 0）の形式となる部分配列の個数」を求める方法について詳しく解説します。配列arr[]と整数Kが与えられたとき、合計がK^m（mは0以上の整数）、すなわちKの非負のべき乗と等しくなる部分配列の数を求める必要があります。

入力: arr[] = { 2, 2, 2, 2 } K = 2

出力: 8

以下のインデックスを持つ部分配列が有効です:
[1, 1], [2, 2], [3, 3], [4, 4], [1, 2],
[2, 3], [3, 4], [1, 4]

入力: arr[] = { 3, -6, -3, 12 } K = -3

出力: 3

この問題を解くためのアプローチとしては、主に次の2つが考えられます。

総当たり法（ブルートフォース）

このアプローチでは、すべての部分配列を順番に調べ、その合計がKの非負の整数べき乗になっているかどうかを確認します。条件を満たしていればカウントを1つ増やします。

実装例

#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int main(){
    int arr[] = {2, 2, 2, 2}; // 与えられた配列
    int k = 2; // 与えられた整数
    int n = sizeof(arr) / sizeof(arr[0]); // 配列のサイズ
    int answer = 0; // カウンタ変数
    for(int i = 0; i < n; i++){
        int sum = 0;
        for(int j = i; j < n; j++){ // このループですべての部分配列を生成
            sum += arr[j];
            int b = 1;
            while(b < MAX && sum > b) // k^m の上限は10^6
                b *= k;
            if(b == sum) // b == sum ならカウントを増やす
                answer++;
        }
    }
    cout << answer << "\n";
}

出力

8

しかし、このアプローチはあまり優れていません。このプログラムの時間計算量はO(N×N×log(K))であり、Nは配列のサイズ、Kはユーザーが与える整数です。

制約が大きい場合、処理に非常に長い時間がかかってしまうため、この計算量では大きな入力には対応できません。そこで、より高い制約にも対応できるよう、別のアプローチを試してみましょう。

効率的なアプローチ

このアプローチでは、累積和（プレフィックスサム）とマップを組み合わせて処理を削減し、時間計算量を大幅に減らします。各位置から右側を見て、目的のべき乗との差に相当する累積和がマップ内にいくつ存在するかを数えることで、高速に答えを求められます。

実装例

#include <bits/stdc++.h>
#define ll long long
#define MAX 1000000
using namespace std;
int main(){
    int arr[] = {2, 2, 2, 2}; // 与えられた配列
    int n = sizeof(arr) / sizeof(arr[0]); // 配列のサイズ
    int k = 2; // 与えられた整数
    ll prefix_sum[MAX];
    prefix_sum[0] = 0;
    partial_sum(arr, arr + n, prefix_sum + 1); // 累積和配列の作成
    ll sum;
    if (k == 1){
    // k == 1 の場合は別途チェックする
        sum = 0;
        map<ll, int> m;
    for (int i = n; i >= 0; i--){
        // m[a+b] = c ならば、c を現在の合計に加える
        if (m.find(prefix_sum[i] + 1) != m.end())
            sum += m[prefix_sum[i] + 1];
            // 累積和の出現回数を増やす
            m[prefix_sum[i]]++;
        }
        cout << sum << "\n";
    }
    else if (k == -1){
        // k == -1 の場合は別途チェックする
        sum = 0;
        map<ll, int> m;
        for (int i = n; i >= 0; i--){
            // m[a+b] = c ならば、c を現在の合計に加える
            if (m.find(prefix_sum[i] + 1) != m.end())
                sum += m[prefix_sum[i] + 1];

            if (m.find(prefix_sum[i] - 1) != m.end())
                sum += m[prefix_sum[i] - 1];

            // 累積和の出現回数を増やす
            m[prefix_sum[i]]++;
        }
        cout << sum << "\n";
    }
    else{
        sum = 0;
        ll b;
        map<ll, int> m;
        for (int i = n; i >= 0; i--){
            b = 1;
            while (b < MAX){ // 10^6 を超える値はチェックしない
                // m[a+b] = c ならば、c を現在の合計に加える
                if (m.find(prefix_sum[i] + b) != m.end())
                    sum += m[prefix_sum[i] + b];
                    b *= k;
            }
            m[prefix_sum[i]]++;
        }
        cout << sum << "\n";
    }
    return 0;
}

出力

8

まとめ

今回は、「合計がk^m（m ≥ 0）の形式となる部分配列の個数」を求める問題を、O(n log(k) log(n))の時間計算量で解きました。総当たり法と累積和＋マップを使った効率的なアプローチの両方を実装し、それぞれの考え方とC++プログラムを学びました。同じロジックはC言語、Java、Pythonなど他の言語でも同様に実装できます。本記事が皆さんのお役に立てれば幸いです。