削除操作後の配列の最短サイズを求めるC++プログラム

n個の要素を持つ配列Aがあるとします。この配列に対して、次のような操作を適用することを考えます。操作の内容は、「互いに異なる値を持つ隣接する2つの要素を取り除き、その位置にそれらの合計値を配置する」というものです。この操作を1回行うごとに、配列のサイズは1ずつ減少していきます。ここでの課題は、操作を実行した後に到達可能な配列の最短の長さを求めることです。

例えば、入力が A = [2, 1, 3, 1] の場合、出力は 1 になります。まず (1, 3) を選ぶと配列は [2, 4, 1] となり、次に (2, 4) を選んで [6, 1] とし、最後に残りの2つを選ぶことで [7] が得られるためです。

解決手順

この問題を解くために、以下の手順に従います。

n := Aのサイズ
集合 se を1つ定義する
i := 0 で初期化し、i < n の間、i を1ずつ増やしながら繰り返す:
    se に A[i] を挿入する
もし se のサイズが 1 と等しい場合:
    n を返す
そうでなければ:
    1 を返す

考え方のポイント

このアルゴリズムの鍵となるのは、「配列内のすべての要素が同一の値であるかどうか」を判定することです。set を使えば重複を除去できるため、集合のサイズが1なら全要素が同じ値だと分かります。

• 全要素が同一の場合： 操作の前提条件である「互いに異なる隣接要素」が存在しないため、どの操作も実行できません。よって答えは n のままです。
• 異なる要素が1つでも存在する場合： 合計値を配置する操作を繰り返すことで、必ず配列を1つの要素まで縮小できます。よって答えは 1 になります。

この手法により、時間計算量 O(n log n)、空間計算量 O(n) で効率的に答えを求められます。

実装例

理解を深めるために、以下のC++による実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
    int n = A.size();
    set<int> a;
    for (int i = 0; i < n; i++) {
        a.insert(A[i]);
    }
    if (a.size() == 1)
        return n;
    else
        return 1;
}
int main() {
    vector<int> A = { 2, 1, 3, 1 };
    cout << solve(A) << endl;
}

入力

{ 2, 1, 3, 1 }

出力

1