AGC-010-A Addition

■■■問題■■■

黒板にN個の整数が書かれています。i番目の整数はAiです。
これらの数に対して、高橋君は以下の操作を繰り返します。

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

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

■■■入力■■■

N
A1 A2 ・・・ AN

●2 <=  N <= 10万
●1 <= Ai <= 10億
●Aiは整数

■■■出力■■■

黒板に数1つだけ残るようにできるならYESを、そうでないならNOを出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("1 2 3");
            //YES
            //以下のようにすれば、数を1つだけ残すことができます。
            //●黒板から1と3を消し、4を書く。このとき、残る数は(2,4)である
            //●黒板から2と4を消し、6を書く。このとき、残る数は6だけである
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("1 2 3 4 5");
            //NO
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        int OddCnt = wkArr.Count(X => X % 2 == 1);

        //奇数の個数が2の倍数ならOK
        Console.WriteLine(OddCnt % 2 == 0 ? "YES" : "NO");
    }
}

解説

偶数 + 偶数 = 偶数
奇数 + 奇数 = 偶数
ですので、

1個以上の偶数は、1個の偶数にできます。

奇数は、2の倍数個あれば、偶数のみにできて
2の倍数個でなければ、1個の偶数と1個の奇数にしかできません。

以上をふまえて、奇数の個数が2の倍数かを判定してます。