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

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

AtCoder AGC 010 A - Addition (300 点)

メッチャシンプルで大好きなパリティ問題!!!
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;
}