きままにものづくり

日々の気付いたことなんかを書いてます。

SRM640Div1Medium

問題

サイズがN1とN2の二部グラフが与えられる。グラフが以下の条件を満たす時のエッジの最大値を求めよ。

  • マッチングの値がc
  • 各頂点の次数がd以上

解法

問題の条件を満たす時のエッジの数を方程式で表現し、それの最大値を計算することで答えが求まる。
N1とN2で大きい方の値をa、小さい方の値をbとする。
a = max(N1,N2)
b = min(N1,N2)

エッジの数をf(v)で表現する。
まず、bのグラフの中からv個の頂点を選び、aの全ての頂点にエッジを張る。
次に、選ばなかった(b-v)個の頂点から、aの中のc-v個の頂点にエッジを張る。
この時のエッジの数は以下の式で表される。また、この時のマッチングはcとなる。
f(v) = av + (b-v)*(c-v)
この式を展開する。
f(v) = v^2 + (a-b-c)v + bc
式の形より、下に凸な2次関数であることがわかる。
よって、エッジの最大値はvの最大値もしくは、最小値の時のf(v)となる。
vの最小値は0である。
vの最大値を考える。
問題の条件により、各頂点の字数はd以上でなければならない。よって、(c-v)はd以上となる。
c-v \leq d
この不等式により、vの最大値はc-dとなる。
f(0)とf(c-d)を計算し、大きい方が答えとなる。

計算量

O(1)

コード