C++で配列の全要素を削除するために必要な最小操作数を求める方法

問題の概要

整数型の配列 arr が与えられたとき、配列のすべての要素を削除するために必要な最小の操作数を求めるのが課題です。ただし、要素を削除する際には次の制約が課されます。

• 配列から任意の要素を自由に選択でき、その要素で割り切れるすべての要素を一度に配列から削除できる。

例えば、arr[] = {2, 4, 15, 10, 8, 5, 3} の場合、すべての要素を削除するには3回の操作が必要です。

• 2 を選択すると、{2, 4, 10, 8} が削除されます。
• 5 を選択すると、{5, 15} が削除されます。
• 3 を選択すると、{3} が削除されます。

アルゴリズム

1. 配列を昇順にソートし、各要素の出現回数をカウントします。
2. 先頭から順に未処理の要素を調べ、その要素で割り切れるすべての要素を削除済みとしてマークし、結果カウンターを1増やします。

解法のポイント

この問題は貪欲法で効率的に解くことができます。配列をあらかじめ昇順にソートしておけば、選んだ要素の倍数は必ず配列の後ろ側に存在します。そのため、各操作で「まだ削除されていない最小の要素」を選ぶことで、その倍数をまとめて削除でき、操作回数を最小限に抑えられます。

実装例（C++）

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define MAX 100
using namespace std;

int getMinOperations(int *arr, int n){
    int map[MAX] = {0};
    sort(arr, arr + n);
    for (int i = 0; i < n; ++i) {
        map[arr[i]]++;
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (map[arr[i]]) {
            for (int j = i; j < n; ++j) {
                if (arr[j] % arr[i] == 0) {
                    map[arr[j]] = 0;
                }
            }
            ++cnt;
        }
    }
    return cnt;
}

int main(){
    int arr[] = {2, 4, 15, 10, 8, 5, 3};
    cout << "Minimum required operations = " << getMinOperations(arr, SIZE(arr)) << endl;
    return 0;
}

出力

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

Minimum required operations = 3