Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AGC010-A 「Addition」 (300)

beta.atcoder.jp

概要

長さ Nの数列 \{A_i\}が与えられる。このとき、以下の操作を繰り返すことで \{A_i\}の長さを1にできるか判定せよ。

  1.  A_i, A_jの偶奇が一致しているような相違なる i, jを選ぶ。
  2.  A_i, A_j \{A_i\}から消す。
  3.  A_i + A_j \{A_i\}の末尾に挿入する。

制約

  •  2 \leq N \leq 10^5
  •  1 \leq A_i \leq 10^9

解説

まず各値で注目すべきはその偶奇のみなので、それさえ分かれば具体的な数値は必要ない。 さらに操作において値のindexもどうでもいいため、数列中の偶数と奇数の数だけを意識すればいいことになる。

では、操作前後で偶数と奇数の個数がどう変化するだろうか。考えられるのは以下の2通り。

  1.  A_i, A_jがともに偶数
    •  A_i + A_jは偶数
    • よって偶数が1個減る
  2.  A_i, A_jがともに奇数
    •  A_i + A_jは偶数
    • よって奇数が2個減り、偶数が1個増える

以上より偶数は1個ずつ減らすことができるが奇数は2個ずつしか減らすことができない。よって「 \{A_i\}の長さを1にできる」ことの必要十分条件は、「 \{A_i\}に奇数が偶数個含まれる」こととなる。この判定自体は容易だろう。

実装例

#include <iostream>
using namespace std;

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

    int oddcnt = 0;
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        
        // 2で割った余りを足すことで、奇数の場合のみ1を加算
        oddcnt += A % 2;
    }

    cout << (oddcnt % 2 == 0 ? "YES" : "NO") << endl;
    return 0;
}

感想

  • 分かってしまえば実装は200点レベル、なんともAGC-Aらしい。
  • 考察も300点にしては簡単か?