AtCoder AGC 010 A - Addition の理解（パリティ）

Question

AtCoder AGC 010 A - Addition の不明点

AtCoder AGC 010 A - Addition　にて結果が[WA]だったため調べたのですが、
解答コードの理屈がよく分からなかったため質問します。
問題、https://atcoder.jp/contests/agc010/tasks/agc010_a
竸プロの解説ブログをいくつか見ても最後の条件分岐で奇数が偶数個ならYesとする理屈が分かりませんでした。

奇数が奇数個ならNo
偶数が偶数個ならYes
奇数が偶数個ならYes
偶数が奇数個ならYes
を問題から解釈し以下コードを実装しました。

実装ソースコード

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

int main() {
  int N;
  cin >> N;

  vector<int> a(N);

  for(int i = 0; i < N; i++){
    cin >> a.at(i);
  }

  int odd = 0;

  for(int i = 0; i < N; i++){
    if(a.at(i) % 2 == 1){
      odd++;
    }
  }

  if(odd % 2 == 1){
    cout << "No" << endl;
  }else{
    cout << "Yes" << endl;
  }
}

補足

また、奇数が0個にはできない？とするのも不明でした。
なお、整数Anが配列である必要がないのは承知です。

Comments

[1T2R3M4]

奇数＋奇数は偶数。

[kei0105]

奇数が奇数個で操作を繰り返していくと{偶数, 奇数}の二つが残ることになるということでしょうか？

[mjk]

全体の総和が奇数＝奇数が奇数個
全体の総和が偶数＝奇数が偶数個
奇数が奇数個の時にしか全体の総和が奇数にならない。
よって総和の奇数か偶数かだけを判定すれば良い。
と解釈しました。

[mjk]

解説が納得出来ない時は1,2,3,4,5～1,2,3,4,5,6,7,8,9,10くらいの少ないテストケースなどで手計算してみると意外とすんなり理解出来たりしますよ。

Answer 1

公式 AGC 10 解説

偶奇が等しい 2 つの数を足すと、その和は偶数になる。

1+3=4 偶数
2+4=6 偶数

よって、N ≥ 2 より、最後に残る数は偶数でなくてはならない。

直前が
1+3=4 偶数が最後に残る
2+4=6 偶数が最後に残る

逆に、和が偶数ならば、もとの数の中に奇数は偶数個あることになるので、
奇数を 2 つずつのペアにしてその和に置き換えることで、全ての数を偶数にできる。

1+3 + 5+7 = 偶数　= 奇数が偶数個ある(奇数が0個も含む)

このとき、どのような順番でも数は 1 つにできるので十分である。

1+2+3+4+5+6+7+8 = 1+3 + 5+7 + 2+4 + 6+8 = 全て偶数　どのような順番でも良い

よって、合計が偶数かどうかの判定ができればいいので、O(N) で解くことができる。

1+2+3+4+5+6+7+8 = 1+3 + 5+7 + 2+4 + 6+8 = 偶数
1+2+3+4+5+6+7+8+9 = 1+3 + 5+7 + 2+4 + 6+8 + 9 = 奇数　
総和が奇数か偶数かだけを判定すればよい

初めて問題見ましたが解説を1行づつ解釈するとこういうことかと思います。

Comments

[kei0105]

>> 奇数が奇数個の時にしか全体の総和が奇数にならない。
これだとyes, no への条件は実装コードのものだと謝りになるのでしょうか。

if(odd % 2 == 1){
cout << "No" << endl;
}else{
cout << "Yes" << endl;
}

[mjk]

検証してませんが、理屈は一緒なので正解が出ると思いますよ。
奇数の数が奇数個ならNOという条件は、総和が奇数という条件と同じですね。

Answer 2

二つの数を消し、その総和を書き加えるので、操作の前後で黒板上の数の総和は変わりません。
さらに偶数どうしか奇数どうしで消すので、書き加えられる数は必ず偶数です。
したがって、最後に一つだけ残るなら、それは偶数であって、最初の数の総和です。
つまり、**「一つだけ残る　⇒　総和が偶数」**が真であることがわかります。

逆に、総和が偶数である場合、

奇数の個数	偶数の個数	総和
偶数	偶数	偶数
偶数	奇数	偶数
奇数	偶数	奇数
奇数	奇数	奇数

この表から、奇数が偶数個である場合に限ることがわかります。
奇数が偶数個であれば、奇数をペアで使い切ることができ、すべて偶数の状態にできます。
偶数ペアはすべて偶数になるので、最終的に一つにできます。
これにより、**「総和が偶数　⇒　一つだけ残る」**も真であることがわかります。

つまり、**「一つだけ残る」と「総和が偶数」は同値な条件であり、
また、先述の表から「総和が偶数」と「奇数が偶数個」**も同値な条件であることがわかります。

同値な条件は、どれを判定しても同じ結果となるので、どれでやってもいいのです。

Comments

[kei0105]

偶数が偶数個の時の奇数が〇〇個のように、
偶数or奇数の一方の個数が分かった上でのもう一方の奇遇数を考慮しなければならないことが抜けいていたようです。
ありがとうございます。