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

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

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

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

問題へのリンク

問題概要

 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} が含まれていないなら、それを追加すると「奇数個選ぶ方法」になる

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