AOJ1604 デッドロック検出 - ferinの競プロ帳

問題ページ
Deadlock Detection | Aizu Online Judge

考えたこと

とりあえずサンプルを読む
あるスレッドで{1,2}が獲得されてて3を取りたい、別のスレッドで{3}を獲得してて1を取りたい→デッドロック
あるuから次のuまでに同じ数字が2回以上出てくる→デッドロック
命令のi番目まで見たときに獲得してるロックの集合と次に取りたいロックのpairを持っておきたい気持ちになる
上をv[i] = (獲得してるロックの集合,次に獲得するロック)としてもつ
v[i].second が v[j].first に含まれ、v[j].second が v[i].first に含まれ、 v[i].first と v[j].first が共通要素を持たないならデッドロックが起きている
スレッド2個しか使わないのでは（は？）と思ってO(N^2)を書くとサンプルで落ちてる
スレッド3個以上でしかデッドロックにならない場合は当然ある
命令のi番目まで実行していて次の命令を実行したい
このとき命令のj番目まで実行しているスレッドがあると実行できないなら i->j の辺を張る
このグラフ上で閉路が存在したらデッドロックが起きる気がする
有向グラフのループ検出なのでトポロジカルソートをする
出すと落ちる
スレッドは最大10個しかないので長さ11以上の閉路があったとしてもデッドロックにはならない
トポロジカルソートでループに入ってる頂点はわかるのでその頂点集合についてUFで連結成分ごとに分ける
ループごとの長さが分かる気がしたのでこれで出すと落ちる
冷静に考えると閉路がくっついているようなパターンがあって無理
これ高速にするの無理そう
-------解説を見た-------
獲得しているロックの集合Sと次に取るロックがtという状態を取りうるか?
dp[S][t] = (true or false) みたいなDP配列を考える
dp[s1][t1] = dp[s2][t2] = true で s1とs2の共通部分が存在せず、t1 が s2に属するとき dp[s1 | s2][t2] = true も成り立つ
上で考えた通り s1とs2の共通部分が存在せず、t1 が s2に属し、t2 が s1 に属するときデッドロックが生じる
dp配列を更新しつつデッドロックが起きる状態があるか確認していく

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

int dp[1<<10][10];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    string s;
    cin >> s;

    memset(dp, false, sizeof(dp));
    int now = 0;
    bool safe = true;
    REP(i, n) {
      if(s[i] == 'u') now = 0;
      else {
        dp[now][s[i]-'0'] = true;
        if(now & 1<<(s[i]-'0')) {
          safe = false;
          break;
        }
        now |= 1<<(s[i]-'0');
      }
    }

    if(!safe) {
      cout << "UNSAFE" << endl;
      continue;
    }

    REP(s1, 1<<10) REP(t1, 10) {
      if(!dp[s1][t1]) continue;
      // dp[s1][t1] と マージ
      REP(s2, 1<<10) REP(t2, 10) {
        if(!dp[s2][t2]) continue;
        bool cond1 = !(s1&s2) && (s2 & 1 << t1),
             cond2 = !(s1&s2) && (s1 & 1 << t2);
        if(cond1 && cond2) {
          safe = false;
        } else if(cond1) {
          dp[s1 | s2][t2] = true;
        } else if(cond2) {
          dp[s1 | s2][t1] = true;
        }
      }
    }

    if(safe) cout << "SAFE" << endl;
    else cout << "UNSAFE" << endl;
  }

  return 0;
}