【C++】指定したルールに従って要素を削除したときの配列の最小サイズを求める方法

この問題では、n個の数値からなる配列と整数値kが与えられます。与えられたルールに従って要素を削除したとき、配列が取りうる最小のサイズを求めるのが課題です。

問題の概要

配列内の要素数をできるだけ減らすことを目標とします。使用できる削除操作では、一度に3つの要素を削除できます。ただし、削除が可能なのは、次の2つの条件を満たす場合のみです。

• 条件1 — 3つの要素が互いに隣接していること
• 条件2 — 隣接する要素同士の差がkであること。つまり、arr[i + 1] = arr[i] + k かつ arr[i + 2] = arr[i + 1] + k が成り立つこと

入力例

{4, 6, 8, 4, 1, 5}, k = 2

出力例

3

説明

インデックス0、1、2にある要素(4、6、8)に対して1回の削除操作が実行できます。6 = 4 + 2、8 = 6 + 2 という関係が成り立っているためです。削除後、配列のサイズは6から3に減少します。

解決アプローチ

この問題は一見単純に見えますが、実際には少し厄介です。ある削除操作を行った後に初めて、新たに削除条件を満たすようになる組み合わせが現れることがあるからです。例えば、5、6、7の位置にある要素を削除すると、その結果として新しい配列上で3、4、5の要素が隣接し、削除条件を満たすようになるかもしれません。

このように部分問題が重なり合う(オーバーラップする)タイプの問題は、動的計画法(DP)を使って効率的に解くことができます。ここでは、部分問題の計算結果をDPテーブルに保存しておき、必要になった時点で再利用します。この手法はメモ化(memoization)と呼ばれます。

アルゴリズムの流れ

1. calcMinSize関数を定義し、区間[start, end]における配列の最小サイズを再帰的に求めます。
2. すでに計算済みの結果がDPテーブルに存在すれば、それをそのまま返します(メモ化による高速化)。
3. 区間の長さが3未満の場合は、それ以上削除できないため、そのまま長さを返します。
4. まず、start番目の要素を残すケースとして「1 + 残りの区間の最小サイズ」を初期値とします。
5. start番目の要素とペアになる2つの要素i、jを探索します。arr[i] = arr[start] + k、arr[j] = arr[start] + 2*k を満たし、かつ中間の区間[start+1, i-1]と[i+1, j-1]が完全に削除できる場合、3要素を削除した後の残り区間[j+1, end]の最小サイズと比較し、より小さい方を採用します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int DP[MAX][MAX];
int calcMinSize(int arr[], int start, int end, int k){
    if (DP[start][end] != -1)
        return DP[start][end];
    if ((end-start + 1) < 3)
        return end-start +1;
    int minSize = 1 + calcMinSize(arr, start+1, end, k);
    for (int i = start+1; i<=end-1; i++){
        for (int j = i+1; j <= end; j++ ){
            if (arr[i] == (arr[start] + k) && arr[j] == (arr[start] + 2*k)
                && calcMinSize(arr, start+1, i-1, k) == 0
                && calcMinSize(arr, i+1, j-1, k) == 0) {
                minSize = min(minSize, calcMinSize(arr, j+1, end, k));
            }
        }
    }
    return (DP[start][end] = minSize);
}
int main() {
    int arr[] = {4, 6, 8, 4, 1, 5 };
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 2;
    memset(DP, -1, sizeof(DP));
    cout<<"The minimum possible size of the array after removal is "<<calcMinSize(arr, 0, n-1, k);
    return 0;
}

出力

The minimum possible size of the array after removal is 3

まとめ

このように、メモ化を活用した動的計画法を用いることで、削除操作を繰り返し適用した際の配列の最小サイズを効率的に求められます。DPテーブルによるキャッシュのおかげで、同じ部分問題を何度も再計算することを避けることができ、全体的な計算コストを大幅に抑えられます。