kmjp's blog

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

TopCoder SRM 660 Div2 Medium PrivateD2party

Hardは簡単だけど、一方こちらは550ptでもいいかも?
http://community.topcoder.com/stat?c=problem_statement&pm=13824

問題

0~(N-1)番のN人の人がいる。
各人は最大で1名嫌いな人がいる可能性があり、その番号はA[i]である。

このN人を何らかの順番でパーティーに招待したい。
N人が順にパーティーに来たとき、先に自分の嫌いな人がパーティーに参加している場合、その人は帰ってしまう(以後パーティーに参加しない)。

適切な順で人を呼んだ場合、最終的にパーティーに参加する人数は最大何人にできるか。

解法

i番の人がA[i]番の人を嫌う、という情報を有効グラフとして考える。
このグラフをトポロジカルソートして考えると、「今後来る人の中の誰にも嫌われてない人から順に呼べばよい」ということがわかる。
基本的にはこうすると全員呼ぶことができる。
(実際にはトポロジカルソートはしなくても良い。)

ただし例外はこのグラフがループになっている場合で、その場合ループの誰か1人はどうしても嫌いな人が先に来ている状態が生じてしまう。

よって、Nから(長さ2以上の)ループの数を引いたものが答え。
ループはDFSで検出できる。

class PrivateD2party {
	public:
	int vis[51];
	vector<int> A;
	
	bool isloop(int c,int st) {
		if(A[c]==c) return false;
		if(vis[c]!=-1) return vis[c]==st;
		vis[c]=st;
		return isloop(A[c],st);
		
	}
	
	int getsz(vector <int> a) {
		int ret=a.size(),i;
		A=a;
		
		MINUS(vis);
		FOR(i,a.size()) if(vis[i]==-1 && isloop(i,i)) ret--;
		return ret;
	}
}

まとめ

なかなか面白い問題だけど、Div2 Mediumにしてはちょっと難しい?