💨

AGC010 A - Additionのメモ

2023/01/14に公開

AtCoder

競プロ

tech

AGCのAは楽しいと聞いてちょっと試してみました。

考察

まず考えたのは、偶奇が一致する2つの数の和の偶奇はどうなるのかです。
まず偶数2つを足した場合は、偶数になります。また、奇数2つを足しても偶数になりますね。

足したら元の数が消えて足した後の数が残るので、全体から見ると偶数2つを選ぶと偶数が1つ消えるだけ、奇数2つを選ぶとそれらが1つの偶数に変わると考えられます。

なので、仮に偶数しかなかった場合は必ず答えはYESになります。どのように選んだとしても、ただ偶数が1つ消えるだけなので、最終的には必ず偶数1つが残ります。

では奇数しかなかった場合は？
これは、個数が偶数個であればYESになります。偶数個であれば綺麗に2つずつのペアに分けられます。
~~勝手に3人ペアを組むやつらがいて余ってしまう子はいない前提です~~

2つの奇数を足すと偶数になるので、2ずつのペアに分けられた奇数は全て偶数に変えることができます。偶数しかない場合はYESになるのは前述の通りなので、この場合はYESです。

奇数個であれば、逆に答えはNOです。2つずつのペアに分けられた奇数は全て偶数に変えて最終的に偶数1つにまとめられますが、余った奇数はそのままです。数が2つ残るのでNOです。
最初から奇数1つしかなかった場合は別ですが、この問題の場合はNが2以上なのでそのようなケースはありません。

では偶数と奇数が混在した場合はどうなるか？
これは、実は偶数のほうは無視して問題ありません。偶数はいくつあっても、必ず1つの偶数にまとめられます。奇数だけで偶数を作れればそれとまとめてしまえるので、それとは別に偶数がいくつあるのかは全く影響がありません。
また、奇数が奇数個あって奇数が一つ余った場合は、偶数が他にいくつかあってもその奇数を偶数に変えることができないため、やはり偶数がいくつあっても関係ないことになります。

なので結論としては、単純に奇数が奇数個あったら答えはNO、そうでなければYESということになります。

なお今さらですが、この問題では偶奇のみが重要で、具体的にどのような数なのかは関係ないので、全ての組み合わせを試すといったことは不要になります。計算量的にも無理ですし。

実装

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }

    if(a.filter { it % 2 == 1 }.size % 2 == 1) {
        println("NO")
    } else {
        println("YES")
    }
}

(執筆時間：21分40秒)

考察

実装

Discussion