Codeforces ECR #124 : E. Sum of Matchings

4問目から割と難しめだった回。
https://codeforces.com/contest/1651/problem/E

問題

2N頂点の無向グラフが与えられる。
このグラフは、1～N番の頂点と、(N+1)～2N番の頂点ならなる二部グラフを構築している。
また、各頂点の次数は2である。

このグラフにおいて、1≦l≦r≦Nとなる[l,r]の頂点とN+1≦L≦R≦2Nとなる[L,R]の頂点からなる部分誘導グラフの最大マッチング数を考える。
あり得るl,r,L,Rの組み合わせにおける各最大マッチング数の総和を求めよ。

解法

連結成分毎に考える。
次数は2以下なので、連結成分はサイクルかパスになる。
サイクルを成すl,r,L,Rの範囲は容易に求められる。
あとはパスを重複なく数え上げる。
その場合、パスの中点を総当たりし、パスの両端を伸ばしながら、そのパスを包含できるl,r,L,Rの組み合わせを数え上げよう。

vector<int> E[3030];
int N;
int vis[3030];
vector<int> C;
ll ret;

void dfs(int cur) {
	if(vis[cur]) return;
	vis[cur]=1;
	C.push_back(cur);
	FORR(e,E[cur]) dfs(e);
}

ll C2(ll a) {
	return a*(a+1)/2;
}

ll pat(int L,int R,vector<int> ng) {
	if(L>R) {
		if(ng.size()) {
			int x=min(ng[0],ng.back());
			int y=max(ng[0],ng.back());
			return C2(x)+C2(y-x-1)+C2(N-y-1);
		}
		else {
			return C2(N);
		}
	}
	int Lmi=0,Rma=N-1;
	FORR(n,ng) {
		if(n>=L&&n<=R) return 0;
		if(n<=L) Lmi=max(Lmi,n+1);
		if(n>=R) Rma=min(Rma,n-1);
	}
	return (L-Lmi+1)*(Rma-R+1);
	
}

void hoge(vector<int> C) {
	int l=C.size();
	int d=l/2;
	int i;
	FOR(i,l) {
		int Lmi=N-1,Lma=0,Rmi=N-1,Rma=0;
		int a=C[i]%N;
		ret-=C2(N)*(C2(a)+C2(N-1-a));
		for(int k=0,x=i,y=i;k<d;k++) {
			
			if(C[x]<N) {
				Lmi=min(Lmi,C[x]);
				Lma=max(Lma,C[x]);
			}
			else {
				Rmi=min(Rmi,C[x]-N);
				Rma=max(Rma,C[x]-N);
			}
			if(C[y]<N) {
				Lmi=min(Lmi,C[y]);
				Lma=max(Lma,C[y]);
			}
			else {
				Rmi=min(Rmi,C[y]-N);
				Rma=max(Rma,C[y]-N);
			}
			
			x=(x+1)%l;
			y=(y+l-1)%l;
			vector<int> ng1,ng2;
			if(C[x]<N) ng1.push_back(C[x]);
			else ng2.push_back(C[x]-N);
			if(C[y]<N) ng1.push_back(C[y]);
			else ng2.push_back(C[y]-N);
			ret-=pat(Lmi,Lma,ng1)*pat(Rmi,Rma,ng2);
		}
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2*N) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	ret=2*N*C2(N)*C2(N);
	
	FOR(i,N) if(vis[i]==0) {
		C.clear();
		dfs(i);
		hoge(C);
	}
	
	
	ret/=2;
	cout<<ret<<endl;
	
}

まとめ

この数え上げ方は思いつかなかったな…。