C++で変更回数を最小限に抑えて整数配列を狭義単調増加に変換する方法

問題の概要

このチュートリアルでは、変更回数を最小限に抑えて、整数配列を狭義単調増加（厳密に増加する順序）の配列に変換するプログラムについて解説します。

具体的には、整数配列が1つ与えられます。私たちのタスクは、要素の書き換えをできるだけ少ない回数にとどめながら、配列全体を狭義単調増加の順序にすることです。

アルゴリズムの考え方

この問題は、最長増加部分列（LIS: Longest Increasing Subsequence）を求める動的計画法を応用することで解けます。鍵となるのは、「変更せずにそのまま残せる要素」を見抜くための条件です。

インデックス j と i（j < i）にある2つの要素をどちらも変更せずに残すためには、次の2つの条件を満たす必要があります。

• arr[i] > arr[j] … 値が厳密に増加していること
• (i - j) <= (arr[i] - arr[j]) … インデックスの差が値の差以下であること

2つ目の条件は、間に挟まれた要素を整数に書き換えて狭義単調増加にするために不可欠です。インデックスが1つ進むごとに、値は少なくとも1以上増える必要があるためです。

この条件を満たす要素をつなげた最長の列の長さをLISの要領で求め、配列の長さ n からその長さを引けば、必要な最小の変更回数が得られます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
// 必要な変更回数を計算する
int remove_min(int arr[], int n){
    int LIS[n], len = 0;
    for (int i = 0; i < n; i++)
    LIS[i] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && (i-j)<=(arr[i]-arr[j])){
                LIS[i] = max(LIS[i], LIS[j] + 1);
            }
        }
        len = max(len, LIS[i]);
    }
    // 必要な変更回数を返す
    return n - len;
}
int main(){
    int arr[] = { 1, 2, 6, 5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << remove_min(arr, n);
    return 0;
}

出力

2

コードの解説

上記の例では、配列 { 1, 2, 6, 5, 4 } が入力として与えられています。条件を満たして変更せずに残せる要素は、たとえば「1, 2, 6」（インデックス 0, 1, 2）の3つです。したがって、残りの「5」と「4」の2要素を書き換えればよく、出力は 2 となります。

すべての要素ペアを二重ループで調べているため、このアルゴリズムの計算量は O(n²) です。要素数が多い場合は、LISを二分探索で求める O(n log n) の手法への拡張も検討するとよいでしょう。