kmjp's blog

競技プログラミング参加記です

TopCoder SRM 813 : Div1 Easy Div2 Hard PartialRaceResults

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;
		
		
	}
}

まとめ

やるべきことはすぐわかるんだけど、割と実装が増えてめんどいな。