Educational DP Contest / DP まとめコンテスト O - Matching

問題
提出コード(1)
提出コード(2)

解法

bitDPです。
番目までの男子に対してペアを作成し終えた段階で、残っている女子の状態がの際の組み合わせの数
とします。
とりあえず、女子全員が残っている状態をとします。
1人目の男子に対してペアを組める女子を1人選び、から除外した状態をとすると、初期状態はです。これは1人目の男子と相性がいい女子全員が対象です。
の求め方について考えていきます。
人目までのペアを作成し終えているので、人目は、以外の女子の誰かとペアを組んでいるはずです。その女子を含んだ、1つ前の状態をとすると、

となります。

感想

bitDPの解説、難しいと思います(1<<nみたいなのを書いたほうがわかりやすいかもですね)
今回はTLEが怖くて、ビットの部分集合を列挙する方法(提出コード2です)を使ったんですが、終わってから計算しなおしてみたら、その必要はなかったです(しかも実行時間あんまり変わりませんでした)。 思考の流れとしては、まず制約が明らかにビットを使ってください、と言っているようなものなので、そこに目を付けました。男女共にビットを使うと、当たり前ですが時間内に解くことができないので、片方だけビットを使ってうまく解く方法を考えることになります。すると、1人の男子に対する女子の選び方はたかだか通りなので、あとは選んだ後の女子の状態を一緒に持てば解けるだろう、という感じになります。