C++で配列の値から構築できるピラミッド（三角形）の最大高さを求める方法

問題概要

整数の配列が与えられたとき、その配列の値を使って構築できるピラミッド（三角形）の最大の高さを求めます。ただし、ピラミッドは上の段から下の段に向かって、各段が直前の段よりも多くの要素を含み、かつ合計値も大きくなるように構成する必要があります。

例

入力配列が {40, 100, 20, 30} の場合、答えは 2 になります。

最下段に 100 と 20 を配置し、その上の段に 40 または 30 のどちらか一方を置くことで、条件を満たす高さ 2 のピラミッドを作ることができます。

アルゴリズム

この問題の解法は、シンプルな数学的性質に基づいています。高さ h のピラミッドを構築するためには、1 + 2 + 3 + ... + h = h × (h + 1) / 2 個の要素が必要です。したがって、配列の要素数 n に対して、h × (h + 1) / 2 が n を超えない最大の h を求めれば、それが答えとなります。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
int getMaximumHeight(int *arr, int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        long long y = (i * (i + 1)) / 2;
        if (y < n) {
            result = i;
        } else {
            break;
        }
    }
    return result;
}
int main() {
    int arr[] = {40, 100, 20, 30};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Result = " << getMaximumHeight(arr, n) << endl;
    return 0;
}

コードの解説

getMaximumHeight 関数では、i を 1 から順に増やしながら、i 段のピラミッドを構築するために必要な要素数 i × (i + 1) / 2 を計算します。この値が配列の要素数 n より小さい間は、その高さのピラミッドが構築可能であるため、result を更新していきます。必要な要素数が n を超えた時点でループを終了し、最後に更新された result を返します。

このアルゴリズムの計算量は O(n) であり、配列の要素の実際の値には依存しないため、非常に効率的です。

出力

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Result = 2