SRM393 div1 medium
無理やり感が否めない。
基本的にシンボルとパターンを総当りでぶつけていく。
でも、どの電球が生きているのかはパターンすべての中で一回でもついたことのある電球だけ。
パターンiとシンボルjをぶつけるときに、
パターン[i][k]=='1' && シンボル[j][k]=='0' または
電球kが生きている && パターン[i][k]=='0' && シンボル[j][k]
となるkがあったらその組み合わせはあり得ない。
#include <string> #include <vector> using namespace std; class NSegmentDisplay { public: string brokenSegments(vector <string> symbols, vector <string> patterns) { int n=symbols[0].size(); string ans(n,'?'); vector<string> cand; for(int i=0;i<patterns.size();i++) for(int j=0;j<n;j++) if(patterns[i][j]=='1') ans[j]='Y'; for(int pi=0;pi<patterns.size();pi++) { string p(n,'#'); for(int si=0;si<symbols.size();si++) { int i; for(i=0;i<n;i++) { if(patterns[pi][i]=='1' && symbols[si][i]=='0') break; else if(ans[i]=='Y' && symbols[si][i]=='1' && patterns[pi][i]=='0') break; } if(i==n) { if(p[0]=='#') for(i=0;i<n;i++) { if(patterns[pi][i]=='1' && symbols[si][i]=='1') p[i]='Y'; else if(patterns[pi][i]=='1' && symbols[si][i]=='0') ; else if(patterns[pi][i]=='0' && symbols[si][i]=='1') p[i]='N'; else if(patterns[pi][i]=='0' && symbols[si][i]=='0') p[i]='?'; else ; } else { for(i=0;i<n;i++) if(patterns[pi][i]=='1') ; else if(symbols[si][i]=='0') p[i]='?'; } } } if(p[0]=='#') return "INCONSISTENT"; cand.push_back(p); } for(int i=0;i<cand.size();i++) for(int j=0;j<n;j++) if(ans[j]=='?') { ans[j]=cand[i][j]; } else { if(ans[j]!=cand[i][j] && cand[i][j]!='?') return "INCONSISTENT"; } return ans; } };