C++で解く：新しい要素を追加して「任意の2要素の差が配列内に存在する配列」を構成するプログラム

問題の概要

n個の相異なる要素を持つ配列Aが与えられます。配列Bが「良い配列（nice）」であるとは、次の2つの条件を満たすことをいいます。

• B[i] ≠ B[j] を満たす任意の2要素について、絶対差 |B[i] − B[j]| がBの中に少なくとも1回現れること
• Bのすべての要素が互いに重複しないこと

求めたいのは、配列Aにいくつかの整数を追加して、要素数300以下の良い配列を作ることができるかどうかです。可能であれば新しい配列を返し、不可能な場合は -1 を返します。

入力例と出力例

たとえば、入力が A = [4, 8, 12, 6] だった場合、出力は [8, 12, 6, 2, 4, 10] のようになります。実際、この配列では次のすべての絶対差が配列内に存在しています。

• |4−2| = |6−4| = |8−6| = |10−8| = |12−10| = 2
• |6−2| = |8−4| = |10−6| = |12−8| = 4
• |8−2| = |10−4| = |12−6| = 6
• |10−2| = |12−4| = 8
• |12−2| = 10

したがって、この配列は条件を満たす良い配列です（ほかにも正解となりうる配列は複数存在します）。

解法の手順

この問題は、以下のシンプルな方針で解くことができます。

1. まず配列Aの要素を走査します。負の数が1つでも含まれていれば、答えは -1 になります。
2. 負の数が含まれない場合、0 から配列の最大値までのすべての整数を出力します。0〜maxまでの連続した整数を並べれば、任意の2要素の差も必ず同じ範囲内に収まるため、自動的に良い配列の条件を満たします。

擬似コード

n := Aのサイズ
t := 0
b := 0
i := 0 から n 未満の間、1ずつ増やしながら繰り返す：
    a := A[i]
    もし a < 0 ならば：
        t := 1
    b := a と b のうち大きい方
t が 0 以外ならば：
    -1 を出力
そうでなければ：
    i := 0 から b 以下の間、1ずつ増やしながら繰り返す：
        i を出力

C++による実装例

それでは、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> A) {
    int n = A.size();
    int t = 0;
    int b = 0;
    for (int i = 0; i < n; i++) {
        int a = A[i];
        if (a < 0)
            t = 1;
        b = max(a, b);
    }
    if (t)
        cout << "-1";
    else {
        for (int i = 0; i <= b; i++)
            cout << i << ", ";
    }
}
int main() {
    vector<int> A = { 4, 8, 12, 6 };
    solve(A);
}

入力

{ 4, 8, 12, 6 }

出力

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

まとめ

配列に負の数が含まれている場合、良い配列を構成することはできないため -1 を出力します。一方、すべての要素が非负であれば、0から最大値までの連続した整数をすべて並べるだけで、任意の2要素の差が必ず配列内に存在する「良い配列」を簡単に構成できます。計算量はO(n)と非常に効率的です。