TopCoder SRM 393 Div1 Medium NSegmentDisplay

問題

n個のセグメントがあり、patterns[i]のように点灯した。
それぞれは、symbols[]のいずれかを表示している。

symbols[i]およびpatterns[i]は文字列として与えられ、
j文字目が0であるときj番目のセグメントが消えていて、1であるとき点灯していることを示す。

セグメントには故障しているものがいくつかある。
セグメントが正常な場合、表示通りに点灯する。
セグメントが故障している場合、ずっと消えたままである。

それぞれのセグメントについて、正常なら'Y',故障しているなら'N',どちらもありうるならば'?'を書いた文字列を出力せよ。
セグメントの表示が矛盾している場合はINCONSISTENTを表示せよ。

制約条件

n≦50
patterns[i]とsymbols[i]の文字数は全て同じ
symbolsの要素数≦50
patternsの要素数≦50

方針

セグメントの故障状態がひとつ決まったときに、
patternsとsymbolsが完全マッチングをもつとき、その状態はありえるものである。

一度でもついたセグメントは、正常なセグメントである。

一度もつかないセグメントは、正常または故障している可能性がある。
故障か正常かわからない状態では、（パターンからシンボルに対して）
0→1および0→0の対応の両方がとれる。

仮にそのセグメントが故障していたとすると、
0→0の対応と0→1の両方の対応がつく。
故障していないとすると、
0→0の対応しかとれないことになり、対応するパターンが部分集合になる。

なので、'?'であるようなセグメントについて、一文字ずつ'Y'をあてはめて、
二部マッチングが完全マッチングを持つかを確かめ、
完全マッチングを持っていた場合'?'のままで、
そうでないならそのセグメントが'N'になることになる。

ソースコード

int N,p[100];
bool v[100],e[100][100];
bool match(int s){
  if(s<0)return 1;
  rep(i,N)if(!v[i]&&e[s][i]){
    v[i]=1;
    if(match(p[i]))return p[i]=s,p[s]=i,1;
  }
  return 0;
}
vs symbols,patterns;
int n,m,l;
bool ck(string str){
  rep(i,n)rep(j,m){
    e[i][j+n]=e[j+n][i]=1;
    rep(k,l)if(
      symbols[i][k]=='0'&&patterns[j][k]=='1'
      ||str[k]=='Y'&&symbols[i][k]=='1'&&patterns[j][k]=='0'
      ||str[k]=='N'&&symbols[i][k]=='1'&&patterns[j][k]=='1')
      e[i][j+n]=e[j+n][i]=0;
  }
  rep(i,N)p[i]=-1;
  int cnt=0;
  rep(i,n){
    rep(j,N)v[j]=0;
    if(match(i))cnt++;
  }
  return cnt==m;
}

class NSegmentDisplay {
  public:
  string brokenSegments(vector <string> symbols, vector <string> patterns) {
    sort(all(patterns));
    patterns.erase(unique(all(patterns)),patterns.end());
    
    n=symbols.size(), m=patterns.size(), l=symbols[0].size();
    ::symbols=symbols; ::patterns=patterns;
    N=n+m;
    memset(e,0,sizeof(e));
    
    string ans(l,'?');
    rep(i,m)rep(j,l)if(patterns[i][j]=='1')ans[j]='Y';
    rep(i,l)if(ans[i]=='?'){
      ans[i]='Y';
      if(ck(ans))ans[i]='?';
      else ans[i]='N';
    }
    return ck(ans)?ans:"INCONSISTENT";
  }
};