C++で3つのスタックの合計を等しくする最大値を求めるアルゴリズム

正の整数からなる3つのスタックが与えられたとき、先頭要素の削除を許可して、3つのスタックの合計が等しくなる最大値を求める問題を考えてみましょう。スタックは配列として表現され、配列の最初のインデックスがスタックの先頭（トップ）の要素を表します。

例として、スタックの要素が [3, 10]、[4, 5]、[2, 1] である場合を考えます。この場合の出力は 0 になります。なぜなら、3つのスタックすべてから全要素を削除しない限り、合計を等しくできないからです。

アルゴリズムの考え方

この問題を解くための基本的なアイデアは、各スタックの合計値を比較し、等しくなければ合計が最大のスタックから先頭要素を削除するという貪欲法（グリーディ法）です。具体的には、以下の手順に従います。

• まず、各スタックに含まれるすべての要素の合計を求めます。

• 3つのスタックの合計がすべて等しければ、その値が求める最大合計です。

• 等しくない場合は、3つのスタックの中で最も合計が大きいスタックの先頭要素を削除します。その後、手順1と手順2を繰り返します。

この方法により、各スタックの合計を段階的に減らしながら、3つの合計が一致する瞬間を効率的に見つけることができます。いずれかのスタックが空になった時点で合計を等しくできないことが確定するため、その場合は 0 を返します。

実装例

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

int maxStackSum(int stk1[], int stk2[], int stk3[], int size1, int size2, int size3) {
    int add1 = 0, add2 = 0, add3 = 0;
    // 各スタックの合計を計算
    for (int i = 0; i < size1; i++)
        add1 += stk1[i];
    for (int i = 0; i < size2; i++)
        add2 += stk2[i];
    for (int i = 0; i < size3; i++)
        add3 += stk3[i];

    int top1 = 0, top2 = 0, top3 = 0;
    while (true) {
        // いずれかのスタックが空になった場合は等しい合計を作れない
        if (top1 == size1 || top2 == size2 || top3 == size3)
            return 0;
        // 3つの合計が等しければそれが答え
        if (add1 == add2 && add2 == add3)
            return add1;
        // 合計が最大のスタックから先頭要素を削除
        if (add1 >= add2 && add1 >= add3)
            add1 -= stk1[top1++];
        else if (add2 >= add1 && add2 >= add3)
            add2 -= stk2[top2++];
        else if (add3 >= add1 && add3 >= add2)
            add3 -= stk3[top3++];
    }
}

int main() {
    int stack1[] = { 3, 2, 1, 1, 1 };
    int stack2[] = { 4, 3, 2 };
    int stack3[] = { 1, 1, 4, 1 };
    int size1 = sizeof(stack1) / sizeof(stack1[0]);
    int size2 = sizeof(stack2) / sizeof(stack2[0]);
    int size3 = sizeof(stack3) / sizeof(stack3[0]);
    cout << "最大合計は: " << maxStackSum(stack1, stack2, stack3, size1, size2, size3);
}

実行結果

最大合計は: 5

この例では、スタック1の合計は 8、スタック2の合計は 9、スタック3の合計は 7 です。合計が最大のスタック2から先頭要素 4 を削除すると合計は 5 になり、さらに調整を繰り返すことで、3つのスタックの合計が 5 で一致します。したがって、答えは 5 となります。

計算量

このアルゴリズムの時間計算量は O(n1 + n2 + n3) です。ここで n1、n2、n3 はそれぞれのスタックの要素数です。各要素は最大で1回削除されるだけなので、全体として各スタックの要素を一度ずつ処理すればよいことになります。空間計算量は O(1) で、追加のデータ構造は必要ありません。