ICPC 2015 国内予選2015 E デッドロック検出

問題

All Problems

問題概要

10個のスレッドである命令列を実行するとき、デッドロックする可能性があるかどうかを出力せよ

解法

ここに載ってます。
国内予選講評

の時はP(s,t)をまとめてデッドロックの判定が出来ますが、そうでない時は単純に纏めることが出来ません。

例えば、ロックが3種類、スレッドが2個の時、以下のような命令列を考えます
01u12u20u
1スレッドでこの命令列を走査すると、P({},{0}),P({0},{1}),P({},{1}),P({1},{2}),P({},{2}),P({2},{0})が考えられます。

その後、P(s,t)を纏める走査を行うとP({0,1},{2}),P({1,2},{0}),P({2,0},{1})が新たに加わります。

この時、P({0,1},{2})とP({2},{0})が同時に実行されるとデッドロックが起こりますが、P({0,1},{2})はスレッドを2つ使用しているのでこの２つのPが同時に実行されることはありません。

の時はP(s1,t1)とP(s2,t2)のs1とs2が交わらない時、これら２つのPを同時に実行することができるので、デッドロックの可能性を判定してあげれば良いことになります。

コード

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
 
#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double 
 
using namespace std;

#define MAX_N 10005

int N;
string S;

bool input(){
  cin >> N;
  if(N == 0)
    return false;
  cin >> S;
  return true;
}

bool memo[1 << 10][10];

void init(){
  memset(memo, 0, sizeof(memo));
}

class cLock{
public:
  int Lock;
  int nextLock;
  cLock(int _Lock, int _nextLock){
    Lock = _Lock;
    nextLock = _nextLock;
  }
};

int main(){

  while(input()){
    
    init();

    //1つのスレッドで命令列を走査する
    int Lock = 0;
    bool ansFlag = false;
    queue<cLock> que;
    
    for(int i = 0; i < N; i++){
      //保持しているロックを解除する
      if(S[i] == 'u'){
	Lock = 0;
      }
      else{
	int nextLock = S[i] - '0';
	//獲得しようとしたロックが既に保持されていた場合
	if((Lock >> nextLock) & 1){
	  ansFlag = true;
	  cout << "UNSAFE" << endl;
	  break;
	}
	else{
	  que.push(cLock(Lock, nextLock));
	  memo[Lock][nextLock] = true;
	  Lock |= (1 << nextLock);
	}
      }
    }
    
    //UNSAFEの場合はそこで終了
    if(ansFlag)
      continue;

    //10スレッド用いた時にありうるロックの集合を求める
    while(que.size()){

      cLock lock = que.front();
      que.pop();

      for(int lockS = 0; lockS < (1 << 10); lockS++){
	if((lockS & lock.Lock) != 0)
	  continue;
	for(int nextLock = 0; nextLock < 10; nextLock++){
	  if(memo[lockS][nextLock]){
	    if((lockS >> lock.nextLock) & 1 &&
	       !memo[lockS | lock.Lock][nextLock]){
	      memo[lockS | lock.Lock][nextLock] = true;
	      que.push(cLock(lockS | lock.Lock, nextLock));
	    }
	    if((lock.Lock >> nextLock) & 1 &&
	       !memo[lock.Lock | lockS][lock.nextLock]){
	      memo[lock.Lock | lockS][lock.nextLock] = true;
	      que.push(cLock(lock.Lock | lockS, lock.nextLock));
	    }
	  }
	}
      }

    }
    
    for(int lLock = 0; lLock < (1 << 10); lLock++){
      for(int lnextLock = 0; lnextLock < 10; lnextLock++){
	if(!memo[lLock][lnextLock])
	  continue;
	for(int rLock = 0; rLock < (1 << 10); rLock++){
	  if((lLock & rLock) != 0)
	    continue;
	  for(int rnextLock = 0; rnextLock < 10; rnextLock++){
	    if(!memo[rLock][rnextLock])
	      continue;
	    if((lLock >> rnextLock) & 1 &&
	       (rLock >> lnextLock) & 1){
	      ansFlag = true;
	      break;
	    }
	  }
	  if(ansFlag)
	    break;
	}
	if(ansFlag)
	  break;
      }
      if(ansFlag)
	break;
    }
    
    if(ansFlag)
      cout << "UNSAFE" << endl;
    else
      cout << "SAFE" << endl;

  }

  return 0;

}