kmjp's blog

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

Codeforces #309 Div1 D. Nudist Beach

変な問題設定。
http://codeforces.com/contest/553/problem/D

問題

N頂点M辺からなる無向グラフが与えられる。
このグラフのうち、いくつかは選択不可な頂点がある。

選択不可な頂点以外からなる頂点の部分集合をSとする。
各頂点のスコアを、(隣接する選択点の数)/(隣接点の数)とし、Sのスコアは、Sに含まれる各頂点のスコアの最小値とする。

スコアが最大化であるSを求めよ。

解法

Sとして(選択不可な頂点を除いた)全頂点を考える。
そこからpriority_queue等を用いて、スコアの低い点を選択から外していけば良い。
(その際、当然隣接点のスコアは再計算する)。

その過程でS内の最低スコアが最大になる状態を更新していく。

int N,M,K;
int SS[101010];
bitset<101010> cur,mab;
vector<int> E[101010];
double sc[101010];
double ma=-1;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) cur[i]=1;
	FOR(i,K) cin>>x, cur[x-1]=0;
	while(M--) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	set<pair<double,int> > S;
	FOR(i,N) if(cur[i] && E[i].size()) {
		FORR(r,E[i]) SS[i]+=cur[r];
		sc[i]=SS[i]*1.0/E[i].size();
		S.insert({sc[i],i});
	}
	
	while(S.size()) {
		auto r=*S.begin();
		S.erase(S.begin());
		if(ma<r.first) ma=r.first, mab=cur;
		x=r.second;
		cur[x]=0;
		FORR(r2,E[x]) if(cur[r2]) {
			S.erase({sc[r2],r2});
			SS[r2]--;
			sc[r2]=SS[r2]*1.0/E[r2].size();
			S.insert({sc[r2],r2});
		}
	}
	_P("%d\n",mab.count());
	FOR(i,N) if(mab[i]) _P("%d ",i+1);
}

まとめ

Div1Dにしては簡単。