C. Similar Pairs (Codeforces Round #644 Div. 3)

問題

https://codeforces.com/contest/1360/problem/C

問題概要

項数が偶数の整数列が与えられる。この列の項で偶数と偶数、奇数と奇数、または差が1の項どうしでペアを作る時、あまりなしですべての項をペアにすることが可能か答えよ。

考察

まず列の中の偶数の個数を数えます。これが偶数個である場合、列の項数が偶数個であることから奇数も偶数個です。よって、この場合偶数同士のペアと奇数同士のペアをあまりなく作ることができて、答えは"YES"です。

偶数が奇数個だった場合、奇数も奇数個です。この場合は元の列をソートして、隣り合う項の差を確認していきます。

差が1のペアがあればそれをペアにすることで、偶数と奇数を一つずつ消費することができ（差が1ということはどちらかが偶数でもう一方が奇数です）、残った偶数と奇数はともに偶数個になるため、全てペアにすることができ、答えは"YES"です。

差が1のペアがない場合、どうしても偶数も奇数も1つ余ってしまうため答えは"NO"です。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        int even = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] % 2 == 0) even++;
        }
        if (even % 2 == 0) {
            cout << "YES" << endl;
            continue;
        }
        sort(a.begin(), a.end());
        bool ok = false;
        for (int i = 0; i < n - 1; i++) {
            if (a[i] + 1 == a[i + 1]) {
                cout << "YES" << endl;
                ok = true;
                break;
            }
        }
        if (!ok) cout << "NO" << endl;
    }
}

どうでもいい話

この文章を書いていて、偶数が偶数で奇数が偶数で・・・、あーややこしい！！ってなってました。

なので「偶数」と「偶数個」というように表現を変えてみましたが、どんなもんでしょう・・・。