AOJ 1604 デッドロック検出
問題
Deadlock Detection | Aizu Online Judge
解法
dp[今、各スレッドでロックしている資源をあわせたものの集合] = (次にどれかのスレッドが確保する可能性のある資源の集合の集合) みたいにする。
そして最終的に $ \exists S, \exists e \in dp[S], e \subset S $が成り立つとそこで行き止まりになるのでデッドロックとなる。
マージを高速に行いたいので集合を表すデータ構造としてはbitsetを使う。
計算量は $ 3^{10} \times 10 \times 2^{10}/64 + (2^{10})^{2} \times 10 $ くらい
コード
感想
最初紙に書かずに考察していたらひたすらごちゃごちゃしてごちゃごちゃしてごちゃごちゃした。
紙に書くの、大事