kmjp's blog

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

yukicoder : No.2900 Star Divine

なるほど…。
https://yukicoder.me/problems/no/2900

問題

赤青の点からなる二部グラフが与えられる。
各辺は赤点と青点を結んでおり、また各点の次数は1以上である。

このうち、半分以上の点を含む部分誘導グラフで、含まれる青点と隣接する赤点が奇数となるものの一例を求めよ。

解法

乱択で部分誘導グラフに残す赤点を選ぶ。
あとは条件を満たす青点を残すと、そこそこの確率で条件を満たせるようだ。

int T;
int X,Y,M;
set<int> E[202020];
int okA[202020],okB[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>X>>Y>>M;
		FOR(i,X+Y) E[i].clear();
		FOR(i,M) {
			cin>>x>>y;
			E[x-1].insert(y-1);
		}
		
		int sa=0,sb=0;
		while(1) {
			sa=sb=0;
			FOR(i,Y) {
				okB[i]=(rand()<rand());
				sb+=okB[i];
			}
			FOR(i,X) {
				x=0;
				FORR(e,E[i]) x^=okB[e];
				okA[i]=x;
				sa+=x;
			}
			
			if(sa+sb>=(X+Y+1)/2) break;
		}
		cout<<sa<<" "<<sb<<endl;
		FOR(i,X) if(okA[i]) cout<<i+1<<" ";
		cout<<endl;
		FOR(i,Y) if(okB[i]) cout<<i+1<<" ";
		cout<<endl;
	}
		
		
}

まとめ

確率どのぐらいになるんだろうな。