Subtract Operation-Codeforces

投稿日：2022/03/31 更新日:2022/03/31

問題

$n$ 個の整数列が与えられます。数列の中から $x$ を選び取り除きます。そして数列に残っている値すべてに対して $x$ だけ減算します。最後に要素が1つだけ残るのでその値を $k$ にできるか判定してください。

解法

数列 $a_1, a_2, a_3$ を考えてみます。

\begin{aligned} a_1, &a_2, a_3\\ &\downarrow a_1を選びます\\ (a_2 - a_1)&, (a_3 - a_1)\\ &\downarrow (a_2 - a_1)を選びます\\ (a_3 - a_1& - (a_2 - a_1)) = (a_3 - a_2) \end{aligned}

となり、次の減算で前回の減算を打ち消すことが分かります。したがって、2つの組 $a_i, a_j (i \neq j)$ を選びその差が $k$ となるかを判定すればよい問題となりました。

実装

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

string solve(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0;i < n; ++i){
        cin >> a[i];
    }

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

    for(int i = 0;i < n; ++i){
        if(binary_search(a.begin(), a.end(), a[i] - k)){
            return "YES";
        }
    }
    return "NO";
}

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