メッチャシンプルで大好きなパリティ問題！！！
ABS 記事の最終問題の類題にも挙げてる！！！

問題概要

黒板に $N$ 個の整数 $A_1, \dots, A_N$ が書かれています。これらの数に対して、高橋君は以下の操作を繰り返します。

偶奇が等しい 2 つの数 $A_i, A_j$ を一組選び、それらを黒板から消す。
その後、二つの数の和 $A_i+A_j$ を黒板に書く。

最終的に黒板に数が 1 つだけ残るようにできるかどうか判定して下さい。

制約

$2 \le N \le 10^{5}$
$1 \le A_i \le 10^{9}$

考えたこと

ものすごく鮮やかなパリティの問題！！！！！
AtCoder ではよくある！！！

偶数奇数と言われているので、真っ先に

なんらかの量のパリティが毎ターン不変である
なんらかの量のパリティが毎ターンごとに入れ替わる

のどちらかになってないかを疑いたくなる。そんな「なんらかの量」を見出すためには、あれこれ色んな場合を手を動かしていると見えて来る。

実験

実験してみる。

奇数が 0 個 (全部偶数) のとき、最後 1 個にできる。
奇数が 1 個のとき、(偶数, 偶数, ..., 偶数, 奇数) みたいになっていて、最後どうしても (偶数, 奇数) の状態で残ってしまう
奇数が 2 個のとき、(偶数, 偶数, ..., 偶数, 奇数, 奇数) となって、最後の (奇数) の 2 個はまとめて偶数にできて、全部偶数になるので OK
...

とやってみると

奇数が偶数個のとき、OK
奇数が奇数個のとき、NG

という予想が立つ。一応証明してみる (本番ならやらなくてよさそう)

証明

奇数が偶数個のとき、半分ずつペアにして足すことで「すべて偶数」の状態にできるので OK

奇数が奇数個のとき、ここでパリティの考え方を使う！！！

「奇数の個数」

に着目してみると、これはどのように操作を行っても、奇数の個数のパリティは常に不変であることがわかる。よって奇数の個数を 0 にはできない。一方、もし最後に 1 個だけ数字が残るとしたら、それは偶数でなければならない。なぜなら、最後に 1 個だけ残る 1 ターン前を考えると (偶数, 偶数) か (奇数, 奇数) のどちらかで、それを足すと (偶数) になるからだ。。。
これは矛盾である。

#include <iostream>
using namespace std;

int main() {
    int N; cin >> N;
    int oddnum = 0;
    for (int i = 0; i < N; ++i) {
        int a; cin >> a;
        if (a % 2 == 1) ++oddnum;
    }
    if (oddnum % 2 == 0) cout << "YES" << endl;
    else cout << "NO" << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 010 A - Addition (灰色, 300 点)

問題概要

制約

考えたこと

実験

証明