Easy/Medium解けたけど、Mediumが遅くて結構レート落ちた。
https://community.topcoder.com/stat?c=problem_statement&pm=17158&rd=18868
問題
文字列に関し、「文字Xは文字Yの後、文字Zの前にある」という情報がいくつか与えられる。
条件を満たす文字列を構成せよ。
解法
文字列中における登場順に関しY→X、X→Zという順序関係があると考えると、あとはトポロジカルソートすればよい。
map<char,int> M; vector<int> E[66]; int vis[66]; int in[66]; class PartialRaceResults { public: string reconstruct(vector <string> memories) { string S=""; int i; FOR(i,10) S+='0'+i; FOR(i,26) S+='a'+i; FOR(i,26) S+='A'+i; FOR(i,S.size()) { M[S[i]]=i; E[i].clear(); vis[i]=1; } ZERO(in); FORR(a,memories) { E[M[a[2]]].push_back(M[a[0]]); E[M[a[0]]].push_back(M[a[3]]); vis[M[a[0]]]=0; vis[M[a[2]]]=0; vis[M[a[3]]]=0; in[M[a[0]]]++; in[M[a[3]]]++; } int ma=0; queue<int> Q; string ret; FOR(i,S.size()) { if(vis[i]==0) ma++; if(vis[i]==0&&in[i]==0) Q.push(i); } while(Q.size()) { int cur=Q.front(); Q.pop(); ret+=S[cur]; FORR(e,E[cur]) { in[e]--; if(in[e]==0) Q.push(e); } } cout<<ret<<endl; if(ret.size()!=ma) return ""; return ret; } }
まとめ
やるべきことはすぐわかるんだけど、割と実装が増えてめんどいな。