2020-04-09

AtCoder AGC 017 A - Biscuits (緑色, 200 点)

AtCoder AtCoder200点 AGC-A パリティ「選ぶ」と「選ばない」の一対一対応数え上げ問題 Greedy:各要素について独立に考えてよい部分和二項係数式変形コーナーケース緑色diff

これ、知らなくても解ける制約設定だけど、結構大変やね

問題へのリンク

問題概要

$N$ 個の正の整数 $A_{1}, \dots, A_{N}$ が与えられる。これらからいくつか選ぶ方法のうち、総和を 2 で割ったあまりが $P$ となる方法が何通りあるかを求めよ。

制約

$1 \le N \le 50$
$P = 0, 1$

考えたこと

一般に

総和が奇数 ⇔ 和の中に奇数は奇数個 (偶数は何個でもよい)
総和が偶数 ⇔ 和の中に奇数は偶数個 (偶数は何個でもよい)

が成立する。パリティ (偶奇性) が本質なので、 $A$ を偶数グループと奇数グループとに分けて考えることにする。さらにさらに

偶数グループでの選び方
奇数グループでの選び方

はそれぞれ独立に数え上げて、掛け算すればよいのだ。たとえば $A = (2, 2, 1, 1, 1)$ で $P = 1$ のとき、

偶数グループ (2, 2) の中での選び方は $2^{2} = 4$ 通りある
奇数グループ (1, 1, 1) の中からの選び方は $(1), (1), (1), (1, 1, 1)$ の $4$ 通りある

ということなので、答えは $4 \times 4 = 16$ 通りとなる。

偶数グループ

こっちは簡単。偶数グループに所属する要素数を $m$ とすると、 $2^{m}$ 通りになる。

奇数グループ

こっちは実は簡単。順を追って考えよう。所属する要素数を $m$ とすると、

$P = 0$ のとき、奇数は偶数個であればよいので、選び方の総数は、 ${}_{m}{\rm C}_{0} + {}_{m}{\rm C}_{2} + {}_{m}{\rm C}_{4} + \dots$ 通り
$P = 1$ のとき、奇数は奇数個であればよいので、選び方の総数は、 ${}_{m}{\rm C}_{1} + {}_{m}{\rm C}_{3} + {}_{m}{\rm C}_{5} + \dots$ 通り

ということになる。これを素直に計算しても求めることはできる。二項係数計算については、以下の記事を参考に。

drken1215.hatenablog.com

しかし、実はもっと簡単な天才的な方法が存在する。実はこんなことが成り立つのだ。

${}_{m}{\rm C}_{0} + {}_{m}{\rm C}_{2} + {}_{m}{\rm C}_{4} + \dots = 2^{m-1}$
${}_{m}{\rm C}_{1} + {}_{m}{\rm C}_{3} + {}_{m}{\rm C}_{5} + \dots = 2^{m-1}$

これは初めて見るとびっくりするかもしれない。試してみると $m = 6$ のとき

${}_{6}{\rm C}_{0} + {}_{6}{\rm C}_{2} + {}_{6}{\rm C}_{4} + {}_{6}{\rm C}_{6} = 1 + 15 + 15 + 1 = 32$
${}_{6}{\rm C}_{1} + {}_{6}{\rm C}_{3} + {}_{6}{\rm C}_{5} = 6 + 20 + 6 = 32$

が確かに成立している！！！！！
これは結構有名な公式だけど、証明は下の方で書いてみようと思う。

まとめ

$N$ 個の整数のうち、奇数を $m$ 個とすると、偶数は $N-m$ 個になる。 $m = 0$ のときはコーナーケースなので後で処理するとして、 $m \gt 0$ とすると、

偶数グループでの選び方： $2^{N-m}$ 通り
奇数グループでの選び方： $2^{m-1}$ 通り

ということで、掛け算すると

$2^{N-m} \times 2^{m-1} = 2^{N-1}$ 通り

と求められた。驚くべきことに、 $N$ のみに依存する式で書けるのだ。

$m = 0$ のときは

$P = 0$ のときは $2^{N}$ 通り
$P = 1$ のときは $0$ 通り

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

int main() {
    int N, P;
    cin >> N >> P;
    int m = 0;
    for (int i = 0; i < N; ++i) {
        int A; cin >> A;
        if (A % 2 == 1) ++m;
    }
    if (m == 0) cout << (P == 0 ? (1LL<<N) : 0) << endl;
    else cout << (1LL<<(N-1)) << endl;
}

二項係数の式の成り立つ理由

これが成り立つ理由は実は簡単だ。

$m$ 個の中から偶数個選ぶ方法
$m$ 個の中から奇数個選ぶ方法

が互いに一対一に対応することを示せばよいのだ。それを示せれば、この 2 つの場合の数が等しいことがわかる。そして一般に、

${}_{m}{\rm C}_{0} + {}_{m}{\rm C}_{1} + {}_{m}{\rm C}_{2} + \dots + {}_{m}{\rm C}_{m} = 2^{m}$

が成り立っているので、これを半分に分け合うことで、

${}_{m}{\rm C}_{0} + {}_{m}{\rm C}_{2} + {}_{m}{\rm C}_{4} + \dots = 2^{m-1}$
${}_{m}{\rm C}_{1} + {}_{m}{\rm C}_{3} + {}_{m}{\rm C}_{5} + \dots = 2^{m-1}$

が成立するという論証だ。

それでは、「偶数個選ぶ方法」と「奇数個選ぶ方法」とが一対一に対応することを示そう。

「偶数個選ぶ方法」から「奇数個選ぶ方法」への対応
「奇数個選ぶ方法」から「偶数個選ぶ方法」への対応

が両方とも設計できることを示せばよい (数学的には、全単射があることを示すということになる)。「偶数個選ぶ方法」に対して、

もし $A_{1}$ が含まれているなら、それを除去すると「奇数個選ぶ方法」になる
もし $A_{1}$ が含まれていないなら、それを追加すると「奇数個選ぶ方法」になる

ということで、「奇数個選ぶ方法」への対応ができる。逆に「奇数個選ぶ方法」から「偶数個選ぶ方法」への対応も同様にできる。

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

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