TopCoder SRM 640 Div1 Medium MaximumBipartiteMatchingProblem

本番に回答にたどり着けなかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=13446

問題

片方の頂点群がN1個、もう片方の頂点群がN2個ある二部グラフを考える。

• 各頂点につながる辺の数はD以上
• 最大マッチングはA以下

を満たす二部グラフは存在するか。
存在するなら辺の数の最大値を答えよ。

なお、A,D≦min(N1,N2)であることが保証される。

解法

N1≧N2とする。
まずコーナーケースを片付ける。

• N2==Aの時、フルメッシュの二部グラフを作ればよいので辺の数はN1*N2
• 辺がD本あると最大マッチングは最低2*D個作られる。よってA＜2*Dの場合条件を満たす二部グラフはない。

まず辺の数Dは無視して、最大マッチング数がAとなる二部グラフを考える。
N1個各点から、N2個のうちv個とフルメッシュを張ることを考える。

以下の図のうち*で示す上下の点同士を結ぶことに相当する。

********************** (N1個全部)

*******------------    (N2個のうちv個)

次に、N2個のうち残りの(N2-v)個から、N1個のうち(A-v)個にフルメッシュを張る。
以下の図のうち#で示す上下の点同士を結ぶことに相当する。

####****************** (N1個のうちA-v個)

*******############    (N2個のうちN2-v個)

こうすると最大マッチングはA個になる。
辺の数は前者はN1*v、後者は(A-v)*(N2-v)となるので、合わせてf(v)=v^2 + (N1-A-N2)*v + A*N2となる。
これでvに対する２次式f(v)が立った。
あとはいくつか解の候補vごとにf(v)の最大値を求めればよい。

なお、この式は辺の数の条件よりvの値に制限がある。

• v＜Dだと最初に張った点の辺の数がDに満たないので不可
• A-v＜Dだと２回目に張った点の辺の数がDに満たないので不可

よって境界値としてv=0,D,A-D,N1,N2あたりを試すとともに、２次式の極値となるv=(N1-A-N2)/2周辺を試せばよい。

class MaximumBipartiteMatchingProblem {
	public:
	ll N1,N2,A,D;
	ll val(ll v) {
		if(v<D) return -1;
		if(A-v<D) return -1;
		return N1*v + (A-v)*(N2-v);
	}
	
	long long solve(int n1, int n2, int ans, int d) {
		N1=n1,N2=n2,A=ans,D=d;
		
		if(N1<N2) swap(N1,N2);
		if(N2==A) return N1*N2;
		if(A<2*D) return -1;
		ll ret=-1;
		ret=max(ret,val(0));
		ret=max(ret,val(D));
		ret=max(ret,val(A-D));
		ret=max(ret,val(N1));
		ret=max(ret,val(N2));
		ret=max(ret,val((A+N2-N1)/2));
		ret=max(ret,val((A+N2-N1)/2+1));
		return ret;
	}
}

まとめ

こういう実装よりも発想系の問題は思いつかないとつらいな…。