Atcoder A問題

問題
http://agc017.contest.atcoder.jp/tasks/agc017_a
を以下のように
入力された配列の偶数と奇数の個数を調べ
計算量を減らすため階乗の配列をとってから
コンビネーションを計算し答えを出しました。

ほとんど通るのですが
一部のサンプルでWAとなってしまして、試行錯誤しましたがどこが間違っているのかわかりません。
ご指摘いただけるとうれしいです。
よろしくお願いします。

python
1n, p = (int(i) for i in input().split())
2A=[int(i) for i in input().split()]
3an=0
4
5for i in range(0,n):
6    A[i]=A[i]%2
7one=A.count(1)
8zero=A.count(0)
9
10f=[1]
11t=1
12for i in range(1,max(one,zero)+3):
13    t=t*i
14    f.append(t)
15#0
16if p==0:
17    if zero!=0:
18        for i in range(0,zero+1):
19            an+=round(f[zero]/(f[zero-i]*f[i]))
20
21    j=0
22    if one!=0:
23        while j<=one:
24            an+=round(f[one]/round(f[one-j]*f[j]))
25            j+=2
26    if one!=0 and zero!=0:
27        an-=1
28#1
29if p==1:
30    oo=0
31    for i in range(0,zero+1):
32        oo+=round(f[zero]/round(f[zero-i]*f[i]))
33    j=1
34    ll=0
35    if one!=0:
36        while j<=one:
37            ll+=round(f[one]/round(f[one-j]*f[j]))
38            j+=2
39    an=oo*ll
40
41print(an)

_Victorique__

2017/07/10 09:46

これはどういう方針でどう解こうとしているのですか？他人から見たら読む気にならないですよこれ。

nnnyu16

2017/07/10 11:00

おっしゃる通りですね。すみません。質問を書き直します。

行動規範の内容に同意します

回答2件

ベストアンサー

結論から言うと、考え方自体が間違っています。コンビネーションなど出てきませんし、階乗も出てきません。それと、コンビネーションについて、途中計算が浮動少数点数になるような計算をした場合、誤差によって正確にならない場合があります。

偶数と奇数にわけて考えると言うこと自体はいいところです。

###偶数と奇数の性質

問題文を言い換えると、選んだ袋の数の合計について、2で割った余りが0または1になる組合せの数を求める事になります。つまり、合計が偶数か奇数になると言うことです。ここで偶数と奇数の性質について考えます。

偶数同士をいくら足し合わせても偶数になる。
奇数同士を偶数回足し合わせると偶数、奇数回足し合わせると奇数になる。
偶数と奇数を足し合わせると偶数になる。

###全てが偶数の場合

ここで、全てが偶数であると仮定しましょう。性質1.よりどんな組合せであっても合計は偶数になります。つまり、奇数になることはありません。Pが1、つまり奇数になる場合を求める場合は0で固定です。奇数になる組合せがないからです。ではPが0、つまり偶数になる場合はどうでしょう。この場合は、袋をどのように選んでも良いとなるため、一つ一つの袋について選ぶ・選ばないの二択をしていくことです。1番目は選ぶ・選ばないの2通りです。2番目も2通りです。3番目、4番目、、、とずっと2通りの選択です。それぞれの選択は独立しているので、単純に掛け合わせるだけです。つまり、222*...*2と袋の数だけ2を掛けること、いってみれば2の冪乗を求める事になります。袋の数をN個とすると2のN乗、Pythonで書けば2**Nとなります。

よって、全てが偶数であれば、P==0では2**N、P==1では0となります。

###奇数が含まれている場合

次に、一つ以上の奇数が含まれている場合を考えましょう。最初の奇数になる袋だけ除外して考えます。残りのN-1個の袋について、奇数になる組合せをFo(N-1)、偶数になる組合せをFe(N-1)とします。P==0になるのは、奇数の袋を選んで奇数になる組合せ(Fo(N-1))になったときと選ばずに偶数の組合せになったとき(Fe(N-1))です。つまり、Fo(N-1)とFe(N-1)は被りませんので、あわせてFo(N-1)+Fe(N-1)です。さて、N-1個の組合せは奇数パターンと偶数パターンの二つだけですので、その合計は全ての組合せの数、つまり2**(N-1)です。つまり、2**(N-1)がその組合せの数になります。P==1の時も全く同じように考えることができるので、その組合せは同じく2**(N-1)となります。

###まとめ

つまり、「奇数が無い(全てが偶数)の場合」と「奇数がある場合」にわけること。「偶数を求める場合」と「奇数を求める場合」にわけること。この四つの場合分けによって、0、2**(N-1)、2**Nのいずれかになると言うことです。あとは、これをコードにしてしまえば終わりです。Pythonには冪乗演算子があるので、とっても簡単ですね。

どうしてもわからないときだけ見てください。
参考: 私が書いた解答例

投稿2017/07/10 11:34