TopCoder SRM 782 : Div1 Medium RankingStudents

これ厳密に証明せず投げてしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=15976&rd=17900

問題

N人の生徒を順に並べたい。
ただし各生徒以下の条件が与えられる。

• 生徒iは先頭f[i]番目までに並べないといけない。
• 生徒A[j]はB[j]の前にいなければいけない、というルールがいくつか与えられる。

条件を満たす並べ方はできるか。

解法

いくつか解法がありそう。
自分の解法は以下の通り。
まず、複数の条件を連ねて生徒X[k]がY[k]の前にいなければならない、というケースを列挙し、依存関係も含めて自分の後ろに来るべき人数と前に来るべき人数を数え上げる。

「～～までに並べないといけない」を考えると面倒なので、後ろから並べて「ここからはこの人も使うことができる」と考えていこう。
その時、候補のうち前に依存関係が多い人から優先的に使うようにした。

vector<int> E[1010];

vector<int> B[1010];
int A[1024];
int vis[1010];

class RankingStudents {
	public:
	int dfs(int cur,int id) {
		if(cur==id) return 1;
		if(vis[cur]) return 0;
		vis[cur]=1;
		if(cur!=id) {
			B[cur].push_back(id);
			A[id]++;
		}
		int ret=0;
		FORR(e,E[cur]) ret|=dfs(e,id);
		return ret;
	}
	string rankingPossible(int n, vector <int> f, vector <int> a, vector <int> b) {
		int i,x,y,j;
		FOR(i,n) {
			E[i].clear();
			B[i].clear();
			A[i]=0;
		}
		
		FOR(i,a.size()) E[a[i]].push_back(b[i]);
		
		FOR(i,n) {
			ZERO(vis);
			FORR(e,E[i]) if(dfs(e,i)) return "Impossible";
		}
		
		int did[1010]={};
		vector<pair<int,int>> C;
		for(i=n-1;i>=0;i--) {
			FOR(x,n) if(did[x]==0 && f[x]>=i && A[x]==0) {
				C.push_back({B[x].size(),x});
				did[x]=1;
			}
			sort(ALL(C));
			if(C.empty()) return "Impossible";
			x=C.back().second;
			C.pop_back();
			FORR(b,B[x]) A[b]--;
		}
		
		return "Possible";
		
	}
}

まとめ

本番はループ検出に強連結成分分解とか無駄に使ったりしてタイムロス。