AOJ1604 Deadlock Detection

問題リンク

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1604

問題概要

次の処理を行う.
10個のスレッドのうち一つをランダムに選び命令を行う. 仮に命令が数字である場合, 他のスレッドにより数字に対応するロックが獲得されていなければそのロックを獲得する.
また, 命令が $u$ である場合, そのスレッドが獲得したロックを全て解放する.
長さ $n$ の命令列に対し以上の処理を行う場合デッドロックが起こりうるか判定してください.

考えたこと

初めに $u$ を通過することでロックが全て解放されるので, ある $u$ 同士の間の命令列はそれぞれ独立したものと考えることができる.
$k$ 個の命令列があるとして, $C_0, C_1, ..., C_{k-1}$ としておく. また $k$ 番目の命令列の $i$ 番目の命令を $C_{k, i}$ とする.
主にサンプル4から, デッドロックが起こりうるケースは $C_{k, i}$ と $C_{k,i+1}$ の有向グラフを考えたとき有向閉路が存在するときだとわかる.
ただし, $C_{k, i}, C_{k, i+1}$ を使うには $C_{k, 0}$ から $C_{k, i-1}$ が有向閉路に含まれないことが条件となるため次のような動的計画法を行う.

$dp_{i, j, mask} :$ $i$ を始点として, 最後に使ったロックが $j$ であり, すでに使った頂点集合が $mask$ であるようなものが存在するかの二値テーブル.

これは, $dp_{i, i, (i番目のbit)}$ をtrueで初期化しておき, $(u, v)$ の辺を加える際に直前までの頂点集合と $mask$ の $and$ を見て被りがなければ辺を加えることができるので更新する.
最終的に $v$ が始点と一致して, $dp_{s, u, mask}$ がtrueであれば有向閉路が存在することになる.