C++でセットに追加できる差分要素の最大数を求める方法

問題概要

要素数 n の整数集合 arr[n] が与えられたとき、そのセットに追加できる「差分要素」の最大数を求めるのが課題です。ここでの差分とは |a−b| の形で表される値を指し、a と b はどちらも集合に含まれる要素です。つまり、集合の中から生じる差分のうち、重複せず最大となるものの総数を数えます。具体例を見ながら、問題と解き方を理解していきましょう。

入力例と出力例

入力 − set = {1, 5}

出力 − セットに追加できる差分要素の最大数: 1

説明 − 集合内に存在する差分は |1−5| = 4 の1つだけです。

入力 − set = {2, 7, 1, 9}

出力 − セットに追加できる差分要素の最大数: 5

説明 − この集合から得られる差分は以下の通りです。

|2-7| = 5
|7-1| = 6
|1-9| = 8
|2-9| = 7
|7-9| = 2

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

• 整数配列 arr[n] を用意し、集合の各要素の値を格納します。
• 関数 maximum() 内で、以下の手順3〜6を実行します。
• 変数 ele、temp、val を宣言し、いずれも arr[0] の値で初期化します。
• i を 1 から配列のサイズまで、1 ずつ増やしながらループ処理を行います。
  • 配列内のすべての要素の GCD（最大公約数）を求めます。
  • temp には temp と arr[i] のうち大きい方の値を設定します。
• total を temp / val として計算し、max を total から size を引いた値として求めます。
• max を返却し、結果を出力します。

このアルゴリズムのポイントは、GCD を利用することで全要素の組み合わせを総当たりせずに済む点です。最大値を GCD で割ることで、集合が取りうる範囲の要素数を一発で算出でき、そこから既存の要素数を引くことで追加可能な差分要素の数が効率よく求まります。計算量は O(n) と非常に効率的です。

C++サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 差分要素の最大数を求める関数
int maximum(int arr[], int size){
   int ele = arr[0];
   int val = ele;
   int temp = ele;
   for (int i = 1; i < size; i++){
      val = __gcd(val, arr[i]);
      temp = max(temp, arr[i]);
   }
   int total = temp / val;
   int max = total - size;
   return max;
}
int main(){
   int arr[] = { 2, 7, 1, 9};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum difference elements that can added to a set is: "<<maximum(arr, size);
   return 0;
}

実行結果

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

Maximum difference elements that can added to a set is: 5