kmjp's blog

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

Manthan Codefest'18 : E. Trips

レート微増だったのでまぁいいか…。
http://codeforces.com/contest/1037/problem/E

問題

N人の人がおり、初期状態では互いに友人ではない。
ここでM個のクエリが与えられる。
各クエリは、2人の間が友人関係になるというものである。
なお、この友人関係は推移しない。

N人の人をパーティーに呼ぶことを考える。
各人は、友人がK人以上参加するなら参加してくれる。
各クエリの適用後、パーティー参加者が最大何名となるか答えよ。

解法

(K+1)次の完全グラフができると、その(K+1)人が一斉にパーティーに参加してくれるが、これをクエリ毎に判定するのは間に合わない。
逆に、絶対にパーティーに参加しない人を除く、ということを考えよう。

まず最終的な友人関係を考える。
人を頂点、友人関係をグラフの辺とみなすと、次数K未満の頂点に相当する人はパーティーに参加しない。
よって、そのような人を頂点と辺セットで取り除いていこう。

その後、クエリを逆順に辿り、次数K未満になった頂点が現れたらその人を取り除くということを順次行っていくとよい。

int N,M,K;
int A[202020],B[202020];
unordered_set<int> E[202020];
int ok[202020];
int ret[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	
	FOR(i,M) {
		cin>>A[i]>>B[i];
		A[i]--;
		B[i]--;
		E[A[i]].insert(B[i]);
		E[B[i]].insert(A[i]);
	}
	set<pair<int,int>> S;
	FOR(i,N) {
		ok[i]=1;
		S.insert({E[i].size(),i});
	}
	int cur=N;
	
	for(i=M-1;i>=0;i--) {
		while(S.size()) {
			if(S.begin()->first>=K) break;
			x=S.begin()->second;
			S.erase(S.begin());
			if(ok[x]) {
				ok[x]=0;
				cur--;
				FORR(e,E[x]) {
					S.erase({E[e].size(),e});
					E[e].erase(x);
					S.insert({E[e].size(),e});
				}
				E[x].clear();
			}
		}
		ret[i]=cur;
		
		if(E[A[i]].count(B[i])) {
			S.erase({E[A[i]].size(),A[i]});
			E[A[i]].erase(B[i]);
			S.insert({E[A[i]].size(),A[i]});
		}
		if(E[B[i]].count(A[i])) {
			S.erase({E[B[i]].size(),B[i]});
			E[B[i]].erase(A[i]);
			S.insert({E[B[i]].size(),B[i]});
		}
		
	}
	
	
	FOR(i,M) cout<<ret[i]<<endl;
	
}

まとめ

徐々に辺が増えるグラフで完全グラフが必要になりそうになったら、逆順を考えることにしよう…。