7K12 blog

猫でも分かるアルゴリズム解説

Educational DP Contest O - Matching

f:id:tkr987:20200405200317p:plain

https://atcoder.jp/contests/dp/submissions/10980341

  • ビット全探索をする
  • 男[i]に対してnCi全通りの更に男女[i][j]=1になってるj通りのループ

制約が21しかないのでビット全探索が出来そうと推測できる。男性[i]までにマッチングが成立した女性の組み合わせビットをdp[i][bit1]で表す。例えば、bit1=010010なら女性[1]と女性[4]がマッチング成立済みとする。

if (A[i][j] == '1' && bit1のj桁目が1でない) dp[i][bit1のj桁目を1にした値] += dp[i-1][bit1]

各男性[i]に対して各女性[j]とマッチングするかどうか、それぞれに更に [1, 2^{N}]のビットの組み合わせ全て試していけば解ける。ただし、このままだと O(N^{2}*2^{N})=9*10^{8}で計算量的に少々厳しい。

f:id:tkr987:20200405205654p:plain

そこで、毎回 [1, 2^{N}]のビットの組み合わせを試す必要がないように枝刈りする。例えば、男性[3]と女性のマッチングを考えるときにbit1=101111のような組み合わせは無駄になる。男性[3]までにマッチングした女性の組み合わせビットは1が2個しか立ってないような値になるはず。1がP個立っているビットを高速に列挙するアルゴリズムが蟻本p144に載っている。このアルゴリズムを利用すると O(N^{2} \sum (_{n}C_{k}))となりTLEにならずに通る(いまいち計算量が把握できない…)

https://www.wolframalpha.com/input/?i=21+*+21+*+sum+%2821%21%2F%28i%21+*+%2821-i%29%21%29%29%2C+i%3D1+to+21&lang=ja