Make Equal With Mod-Codeforces

問題リンク-Make Equal With Mod

問題

長さ$n$の非負整数列$a_1, a_2, ...,a_n$が与えられます。以下の操作を0回以上行います。

$x \geqq 2$を満たす整数$x$を選び$1 \leqq i \leqq n$を満たす$a_i$を$a_i \mod x$に置き換える。

操作終了後すべての要素を等しくできるか判定してください。

解法

数列に1の存在あり、なしで場合分けします。

1が存在しない場合

$x = \max(a_i)$とします。操作をすれば、数列の最大値は0になります。これを繰り返すことですべての要素を0にすることが可能です。

したがって、1が存在しなければ常に答えはYESとなります。

1が存在する場合

$x \geqq 2$より1をこれ以上小さくすることは不可能です。よって、すべての要素を1にする必要があります。
$x = \max(a_i)-1$と置けば、数列の最大値は1にできます。しかし、数列中に$\max(a_i)-1$が存在すればその値は0となりすべての要素を等しくすることが不可能となります。

したがって、$|a_i - a_j| \neq 1 (1\leqq i,j \leqq n)$であることが必要です。

実装

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

string solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int& i : a)cin >> i;

    sort(a.begin(), a.end());

    bool exist1 = binary_search(a.begin(), a.end(), 1);
    if(!exist1){
        return "YES";
    }

    for(int i = 0;i < n-1; ++i){
        if(a[i+1] - a[i] == 1){
            return "NO";
        }
    }

    return "YES";
}

int main(){
    int t;
    cin >> t;
    while(t--){
        cout << solve() << endl;
    }
    return 0;
}