C++でちょうどK個の部分配列を削除して、全要素が素数となる配列のサイズを最大化する方法

この記事では、正の整数N個で構成される配列Arr[]からちょうどK個の部分配列（連続する要素列）を削除し、残ったすべての要素が素数であり、かつ残りの配列のサイズが最大となるようにする問題を解説します。

問題の例

入力

Arr[]={4, 3, 3, 4, 3, 4, 3} , K=2

出力

3

説明

K=2であるため、削除できる部分配列は2個だけです。ここでは、Arr[0]とArr[3…5]の2つの部分配列を削除します。その結果、残る配列はArr[]={3,3,3}となり、すべての要素が素数で、サイズも最大になります。

入力

Arr[]={7, 6, 2, 11, 8, 3, 12}, K=2

出力

3

説明

Arr[1]とArr[4…6]を削除することで、素数のみからなる配列Arr[]={7,2,11}が残ります。

プログラムで使用するアプローチ

• まず、sieve()関数を呼び出してエラトステネスの篩を用い、すべての素数を別の配列prime[]に格納します。

• MaxSize()関数内では、i=0からi<Nまでループを実行し、合成数のインデックスをすべてint型のベクターvectに格納します。

• 続いて、i=1からi<vect.size()まで別のループを実行し、隣接する2つの合成数の間に存在する素数の個数を計算して、int型のベクターdiffに格納します。

• sort()関数を使用して、ベクターdiffをソートします。

• さらに、i=1からi<diff.size()までループを実行し、diffの累積和（prefix sum）を求めます。これにより、削除する必要のある素数の個数を把握できます。

• if文で解が存在しないケース、すなわちK>Nの場合や、K=0であるのに合成数が配列中に存在する場合をチェックします。

• Kが合成数の個数以上の場合は、すべての合成数を削除します。この際、余分な素数も一緒に削除することになりますが、削除する部分配列の長さを1にすることが最適解を得るポイントです。

• Kが合成数の個数より少ない場合は、合成数を含む部分配列のみを削除し、素数だけからなる区間は削除対象に含めないようにします。

コード例

#include <bits/stdc++.h>
using namespace std;
const int Num = 1e5;
bool prime[Num];
//エラトステネスの篩
void sieve(){
    for (int i = 2; i < Num; i++) {
        if (!prime[i]){
            for (int j = i + i; j < Num; j += i){
                prime[j] = 1;
            }
        }
    }
    prime[1] = 1;
}
int MaxSize(int* arr, int N, int K){
    vector<int> vect, diff;
    //合成数のインデックスを格納
    for (int i = 0; i < N; i++){
        if (prime[arr[i]])
            vect.push_back(i);
    }
    /*隣接する2つの合成数の間にある
    素数の個数を計算*/
    for (int i = 1; i < vect.size(); i++){
        diff.push_back(vect[i] - vect[i - 1] - 1);
    }
    //diffベクターをソート
    sort(diff.begin(), diff.end());
    //diffベクターの累積和を計算
    for (int i = 1; i < diff.size(); i++){
        diff[i] += diff[i - 1];
    }
    //解が存在しないケース
    if (K > N || (K == 0 && vect.size())){
        return -1;
    }
    //長さ1の部分配列を削除
    else if (vect.size() <= K){
        return (N - K);
    }
    /*部分配列を削除する際に
    削除すべき素数の個数を求める*/
    else if (vect.size() > K){
        int tt = vect.size() - K;
        int sum = 0;
        sum += diff[tt - 1];
        int res = N - (vect.size() + sum);
        return res;
    }
}
//メイン関数
int main(){
    sieve();
    int arr[] = { 7, 2, 3, 4, 3, 6, 3, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
    cout<< MaxSize(arr, N, K);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

6