EDPC : Educational DP Contest の O を解いた。
- O - Matching
https://atcoder.jp/contests/dp/tasks/dp_o
- 提出: https://atcoder.jp/contests/dp/submissions/31448187
- 解説 AC https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035
- 最適化余地どころか bitDP さえ見えなかった
- 21 から 221 までは見えた
dp[S] := S の i 番目のビットで i 番目の女性が既にペアになっているときの場合の数と置く- 単純にやると
O(2^{N}N^{2})になるのでSの 1 になったビット数から遷移を減らす
子どもと公園へ。暑さにやられる。
Moonlighter の 2 つめのダンジョンをクリアした。
今日のコミット。
