C++でオブジェクトの配列から最大の高さのピラミッドを構築する方法

ここでは、n個のオブジェクトからなる配列を扱います。各オブジェクトは幅 W[i] を持っており、これらを次の条件を満たすようにピラミッド状に配置することを考えます。

• i番目のレベルの合計幅は、(i+1)番目のレベルの合計幅より小さいこと
• i番目のレベルに含まれるオブジェクトの数は、(i+1)番目のレベルより少ないこと

例えば、重みが [40, 100, 20, 30] の場合、答えは 2 になります。最上部のレベルには 30 を置き、その下のレベルには 20 と 40、さらにその下に 100 を配置します。

貪欲法によるアプローチ

この問題を解くには、貪欲法(グリーディ法)が有効です。基本的なアイデアは、幅の小さいオブジェクトほど上のレベルに配置し、その下のレベルに次のオブジェクトを置いていくというものです。最大のレベル数を得るためには、まず配列をソートし、上から下へ向かってピラミッドを構築していきます。

具体的には、ソート後の配列の最初の要素(最小の要素)を頂上に置きます。その後、その下に「より多くのオブジェクト数」と「より大きい合計幅」を持つレベルを順に積み上げていきます。この手順を繰り返すことで、構築可能な最大のレベル数を求められます。

サンプルコード

#include <iostream>
#include <algorithm>
using namespace std;

int maxLevelPyramid(int objects[], int n) {
    sort(objects, objects + n);
    int ans = 1;
    int prev_w = objects[0];
    int count_p = 1;
    int count_c = 0;
    int curr_w = 0;
    for (int i = 1; i < n; i++) {
        curr_w += objects[i];
        count_c++;
        if (curr_w > prev_w && count_c > count_p) {
            prev_w = curr_w;
            count_p = count_c;
            count_c = curr_w = 0;
            ans++;
        }
    }
    return ans;
}

int main() {
    int boxes[] = {40, 100, 20, 30};
    int n = sizeof(boxes) / sizeof(boxes[0]);
    cout << "Max level of pyramid: " << maxLevelPyramid(boxes, n);
}

実行結果

Max level of pyramid: 2

アルゴリズムのポイント

このコードでは、まず配列を昇順にソートします。その後、頂上のレベル(最小要素1個)を基準として、下のレベルに向かってオブジェクトを追加していきます。現在のレベルの合計幅とオブジェクト数が、直前のレベルを上回った時点で新しいレベルとして確定し、レベル数をカウントアップします。計算量はソートに依存し、O(n log n) で効率的に処理できます。