C++で合計が完全立方数になるトリプレットの個数を数える方法

n個の整数からなる配列が与えられ、その合計が完全立方数と等しくなるすべてのトリプレット（3つの値の組み合わせ）の個数を求めるのが課題です。

完全立方数とは

完全立方数とは、ある整数を3乗した数のことです。たとえば、125は5の3乗なので、125は完全立方数であると言えます。代表的な完全立方数には、1、8、27、64、125などがあります。

この問題では、配列の中から合計が完全立方数となるトリプレット（3つの値のセット）を見つけて数える必要があります。さらに、トリプレットの合計は最大15000までという条件が設けられているため、考えられる立方数は24個だけです。そこで、動的計画法（DP）を活用することで、少ない計算量でこの問題を解くことができます。

具体例

入力− array[] = { 5, 2, 18, 6, 3 };
出力− トリプレットの数 = 1
説明− 18+6+3 = 27（完全立方数）
これ以外に完全立方数となるトリプレットはありません。

入力− array[] = {1, 2, 3, 4, 5};
出力− トリプレットの数 = 2
説明− 1 + 2 + 5 = 8（完全立方数）
1 + 3 + 4 = 8（完全立方数）

プログラムで使用するアプローチ

• 正の整数からなる配列を入力として受け取る

• 配列のサイズを計算する

• 動的計画法を用いて、配列内の各数値の出現状況を記録する

• トリプレットの個数を格納するための変数ansを初期化する

• 配列を走査し、トリプレットの3番目の要素に該当する候補を探して、合計が完全立方数になるかどうかを判定する。完全立方数であれば、ansの値を1増やす

• 最後にansを返す

コード例

#include <bits/stdc++.h>
using namespace std;
int arrd[1001][15001];
// 指定された範囲内である数値の
// 出現回数を求める関数
void compute(int ar[], int num){
    for (int i = 0; i < num; ++i) {
        for (int j = 1; j <= 15000; ++j) {
            // i == 0 の場合
            // 現在の値に1を代入
            if (i == 0)
            arrd[i][j] = (j == ar[i]);
            // それ以外の場合は、前の状態に
            // 現在の状態を加算
            else
            arrd[i][j] = arrd[i - 1][j] + (ar[i] == j);
        }
    }
}
// 合計が完全立方数となるトリプレットを
// 数える関数
int countTriplets(int ar[], int num){
    compute(ar, num);
    int ans = 0; // 回答を初期化
    for (int i = 0; i < num - 2; ++i) {
        for (int j = i + 1; j < num - 1; ++j) {
            for (int k = 1; k <= 24; ++k) {
                int cube = k * k * k;
                int rem = cube - (ar[i] + ar[j]);
                // j+1からnまでの範囲にある
                // 3番目の要素の出現をすべてカウント
                if (rem > 0)
                ans += arrd[num - 1][rem] - arrd[j][rem];
            }
        }
    }
    return ans;
}
// main関数のコード
int main(){
    int ar[] = { 5, 2, 18, 6, 3 };
    int num = sizeof(ar) / sizeof(ar[0]);
    cout << “トリプレットの数 = ”<<countTriplets(ar, num);
    return 0;
}

出力結果

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

トリプレットの数 = 1