C++で配列の最小調整コストを求める方法

概念

正の整数からなる配列が与えられたとき、隣接する要素同士の差が指定されたtarget以下になるように、配列内の各要素を置き換えることを考えます。このとき私たちの課題は、調整コスト(新しい値と元の値の差の総和)を最小化することです。つまり、Σ|A[i] − A_new[i]|(0 ≤ i ≤ n−1)を最小化する必要があります。ここで、nは配列A[]のサイズ、A_new[]は隣接要素間の差がtarget以下となるように調整した配列を表します。なお、配列のすべての要素は定数M=100より小さいものと仮定します。

入力例

arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20

出力例

Minimum adjustment cost is 35

解法のアプローチ

調整コスト Σ|A[i] − A_new[i]| を最小化するためには、すべてのインデックスiについて |A[i] − A_new[i]| をできるだけ0に近づける必要があります。さらに、次の条件も満たさなければなりません。

|A[i] − A_new[i+1]| ≤ target

この問題は、動的計画法(DP)を用いることで効率的に解くことができます。

A[i]をjに変更したときの最小調整コストをdp1[i][j]とすると、DPの漸化式は次のように定義されます。

dp1[i][j] = min{dp1[i − 1][k]} + |j − A[i]|

ただし、|k − j| ≤ target を満たすすべてのkが対象となります。

ここで、0 ≤ i ≤ n、0 ≤ j ≤ M(nは配列の要素数、M=100)です。したがって、max(j − target, 0) ≤ k ≤ min(M, j + target) の範囲にあるすべてのkの値を考慮します。最終的に、配列全体の最小調整コストは、0 ≤ j ≤ M における min{dp1[n − 1][j]} として求められます。

C++による実装例

// C++プログラム:配列の最小調整コストを求める
#include <bits/stdc++.h>
using namespace std;
#define M1 100

// 配列の最小調整コストを求める関数
int minAdjustmentCost(int A1[], int n1, int target1){
    // dp1[i][j] は A1[i] を j に変更したときの最小調整コストを格納
    int dp1[n1][M1 + 1];
    // 配列の最初の要素は別途処理する
    for (int j = 0; j <= M1; j++)
        dp1[0][j] = abs(j - A1[0]);
    // 残りの要素に対して処理を実行
    for (int i = 1; i < n1; i++){
        // A1[i] を j に置き換えた場合の最小調整コスト dp1[i][j] を計算
        for (int j = 0; j <= M1; j++){
            // 最小調整コストを INT_MAX で初期化
            dp1[i][j] = INT_MAX;
            // k >= max(j - target1, 0) かつ
            // k <= min(M1, j + target1) となるすべての k を考慮して最小値を取る
            for (int k = max(j-target1,0); k <= min(M1,j+target1); k++)
                dp1[i][j] = min(dp1[i][j], dp1[i - 1][k] + abs(A1[i] - j));
        }
    }
    // DPテーブルの最終行から最小値を返す
    int res1 = INT_MAX;
    for (int j = 0; j <= M1; j++)
        res1 = min(res1, dp1[n1 - 1][j]);
    return res1;
}

// 上記の関数をテストするドライバプログラム
int main(){
    int arr1[] = {56, 78, 53, 62, 40, 7, 26, 61, 50, 48};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int target1 = 20;
    cout << "Minimum adjustment cost is "
         << minAdjustmentCost(arr1, n1, target1) << endl;
    return 0;
}

出力

Minimum adjustment cost is 35

まとめ

この問題は、各要素を取りうる値(0〜M)ごとに最小コストを記録していく動的計画法によって解けます。計算量はO(n × M × target)程度となり、要素数や値の範囲が限られている場合に非常に有効なアプローチです。隣接要素の差に関する制約を満たしながら、元の配列からの変更量を最小限に抑えたい場面で応用できます。