みんなのプロコン 2018 決勝 : E - ネットワークの構築

これは本番出ててもできなさそう。
https://beta.atcoder.jp/contests/yahoo-procon2018-final-open/tasks/yahoo_procon2018_final_e

問題

1～Nのラベルが付いたN頂点のグラフを考える。
初期状態では辺はない。

ここで２つの整数集合A,Bが与えられる。
いずれもM要素であり、頂点の番号が格納されている。

A[i]とB[j]を選び、いずれかの向きの有向辺を張る、ということをM回行う。
なお、同じi,jは2回利用できない。
この時、有向辺を辿ると任意の頂点から任意の頂点に遷移できるようにできるか。

解法

橋ができると、明らかに条件を満たせない。
逆にそうでなければ、すなわちA,B問わず全頂点次数が２以上であれば、条件を満たす辺の張り方ができることを示す。

頂点群を以下の３つに分類する。
X:= 頂点ラベルvがAにのみ(2回以上)含まれる頂点
Y:= 頂点ラベルvがBにのみ(2回以上)含まれる頂点
Z:= それ以外、すなわちA,B両方に1回以上含まれる頂点

まず、X,Yに含まれる頂点を、min(|X|,|Y|)個だけ交互に、X1->Y1->X2->Y2->X3->Y3-> ...のようにつなぐ。
その末尾Ynから、Zに含まれる頂点を全部1回ずつつなぎ、X1につないでいこう。
すなわちX1->Y1->X2->Y2->X3->Y3-> ... -> Yn -> Z1 -> Z2 -> ... -> Zm ->X1のようにする。

こうするとこれらの頂点群は閉路に含まれる。

X

と

Y

に差があるとき、例えば

X

＞

Y

の場合、

X

のうちいくつか閉路に登場しない。

ただ、この時未使用のB[j]が|X|の余った数の分の倍以上まだあるはずなので、|X|のうち余った物は、残ったB[j]を2つずつ持ってきて小さな閉路を作っていき、最初に作った大きな閉路に連結していけばよい。

こうすると全頂点を含む閉路が構築できる。
まだ余った辺は適当に追加すればよい。

int N,M;
int A[202020];
int B[202020];
int C[202020];
int D[202020];
vector<int> V[4],AR,BR;
vector<vector<int>> R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) cin>>x, C[x-1]++;
	FOR(i,M) cin>>x, D[x-1]++;
	
	FOR(i,N) {
		if(C[i]+D[i]<2) return _P("No\n");
		if(D[i]==0) V[0].push_back(i);
		else if(C[i]==0) V[1].push_back(i);
		else V[2].push_back(i);
	}
	
	
	int L=min(V[0].size(),V[1].size());
	if(L==0) {
		FOR(i,V[2].size()) {
			R.push_back({V[2][i],V[2][(i+1)%V[2].size()],1});
			C[V[2][i]]--;
			D[V[2][i]]--;
		}
		
	}
	else {
		FOR(i,L) {
			R.push_back({V[0][i],V[1][i],1});
			C[V[0][i]]--;
			D[V[1][i]]--;
			if(i<L-1) {
				R.push_back({V[0][i+1],V[1][i],0});
				C[V[0][i+1]]--;
				D[V[1][i]]--;
			}
		}
		int last=V[1][L-1];
		FORR(v,V[2]) {
			R.push_back({v,last,0});
			C[v]--;
			D[last]--;
			last=v;
		}
		R.push_back({V[0][0],last,0});
		C[V[0][0]]--;
		D[last]--;
	}
	

	FOR(i,N) FOR(x,C[i]) AR.push_back(i);
	FOR(i,N) FOR(x,D[i]) BR.push_back(i);
	for(i=L;i<V[0].size();i++) {
		x=BR.back();
		BR.pop_back();
		y=BR.back();
		BR.pop_back();
		R.push_back({V[0][i],x,1});
		R.push_back({V[0][i],y,0});
		C[V[0][i]]--;
		C[V[0][i]]--;
		D[x]--;
		D[y]--;
	}
	for(i=L;i<V[1].size();i++) {
		x=AR.back();
		AR.pop_back();
		y=AR.back();
		AR.pop_back();
		R.push_back({x,V[1][i],1});
		R.push_back({y,V[1][i],0});
		D[V[1][i]]--;
		D[V[1][i]]--;
		C[x]--;
		C[y]--;
	}
	
	AR.clear();
	BR.clear();
	FOR(i,N) {
		while(C[i]) C[i]--, AR.push_back(i);
		while(D[i]) D[i]--, BR.push_back(i);
	}
	FOR(i,AR.size()) R.push_back({AR[i],BR[i],0});
	
	assert(R.size()==M);
	cout<<"Yes"<<endl;
	FORR(v,R) cout<<(v[0]+1)<<" "<<(v[2]?"<":">")<<" "<<(v[1]+1)<<endl;
}

まとめ

言われてみれば単純だけど、こういうの本番の緊張の中で解ける気はしない。