C++で変更後の配列の最小値が取りうる最大値を求める方法

問題概要

この問題では、サイズnの配列arr[]と数値Sが与えられ、変更後の配列における最小値の最大可能値を求めます。

配列を変更する際には、以下のルールが適用されます。

• 変更前と変更後の配列要素の合計の差は、ちょうどSでなければならない
• 変更後の配列に負の値は許されない
• 変更後の配列の最小値を最大化する必要がある
• 配列の変更は、任意の要素を増加または減少させることによって行える

これらの制約のもとで新しい配列を構成し、その中で最小となる要素の値が最大になるようにします。

例を使って問題を理解しましょう。

入力 : arr[] = {4, 5, 6} S = 2
出力 : 4

説明

この場合、変更後の配列は {4, 5, 5} となり、最小値は4です。これが達成できる最大の最小値となります。

解法アプローチ

変更後の配列の最小値を最大化することが目的です。この問題は、0（最小可能値）からarr_min（最大可能値）までの範囲で、最小値の候補に対して二分探索を行うことで効率的に解けます。各候補値について、制約を満たせるかどうかを判定していきます。

判定条件の考え方

すべての要素をx以上に保つとき、合計を減らせる最大量は「元の配列の合計 − x × n」です。この値がS以上であれば、合計をちょうどSだけ減らしながら全要素をx以上に維持できます。したがって、この条件を満たす最大のxを二分探索で求めればよいのです。

特別なケース

• Sが配列の合計より大きい場合：解は存在しません（-1を返す）
• Sが配列の合計と等しい場合：最小要素の値は0になります

実装例

ソリューションの動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;
int findmaximisedMin(int a[], int n, int S){
   int minVal = a[0];
   int arrSum = a[0];
   for (int i = 1; i < n; i++) {
      arrSum += a[i];
      minVal = min(a[i], minVal);
   }
   if (arrSum < S)
      return -1;
   if (arrSum == S)
      return 0;
   int s = 0;
   int e = minVal;
   int ans;
   while (s <= e) {
      int mid = (s + e) / 2;
      if (arrSum - (mid * n) >= S) {
         ans = mid;
         s = mid + 1;
      }
      else
         e = mid - 1;
   }
   return ans;
}
int main(){
   int a[] = { 4, 5, 6 };
   int S = 2;
   int n = sizeof(a) / sizeof(a[0]);
   cout<<"The maximum value of minimum element of the modified array is "<<findmaximisedMin(a, n, S);
   return 0;
}

出力

The maximum value of minimum element of the modified array is 4

まとめ

本記事では、配列の要素を増減させて合計の差をSに一致させながら、変更後の配列の最小値を最大化する問題を扱いました。二分探索を用いることで、候補値ごとに線形に確認する方法よりも大幅に効率的に、O(n log(arr_min)) の時間計算量で最適解を求められます。