DP O
21個のものの順列のうち、特定の条件を満たすものを数え上げる問題
先頭を一つ決めて、残りの20個の順列を考える場合に「使えるもの」が21通りある
というわけで「使えるもの」を定義域とし、条件を満たすものの個数を値とするDP
「使えるもの」は高々21個の集合の部分集合なので2^21、およそ10^7
小さい集合の部分集合を列挙するのはビット演算を使うと速い(生Pythonではそれほどでもないが)
bitDPと呼ぶ人もいるのかな
生PythonではTLEしそうだったが、PyPyなら AC
pythondef solve(N, data):
FULLBIT = (1 << N) - 1
memo = [-1] * (1 << N)
def f(cursor, available):
if cursor == N:
return 1
ret = memo[available]
if ret != -1:
return ret
ret = 0
j = 0
m = available
while m:
if m & 1:
# available woman
if data[cursor * N + j]:
# acceptable
ret += f(cursor + 1, available ^ (1 << j))
j += 1
m //= 2
ret %= MOD
memo[available] = ret
return ret
return f(0, FULLBIT)Related Pages
- →アルゴリズム×蟻本×区間スケジューリング×二分探索木×unionfind×最短路問題×最小全域木×ユークリッドの互除法×ニ分探索×しゃくとり法×半分全列挙×座標圧縮×セグメント木×binary_lndexed_tree×バケット法×平方分割×ビットdp×bitDP×行列累乗×繰り返し二乗法×最大流×最小カット×二部マッチング×一般マッチング×マッチング×辺カバー×安定集合×点カバー×最小費用流×凸包×grundy数×強連結成分分解×2-sat×lca×ダブリング×接尾辞配列×sparse_table×rmq×atcoder→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]