No.200

最小費用流を使う.

$N$ 試合分のカードをA君, C君ともに並べる. カード枚数が試合数より少ない場合はA君は数字の大きいカードから順に埋めていき, C君は数字の小さいカードから順に並べる.

始点からA君のカードへ許容量1, コスト0の辺をつなぎ, B君のカードから終点へ許容量1, コスト0の辺をつなぐ. A君のカードからC君のカードへは対戦する可能性のあるカードすべてに許容量1の辺をつなぐ. コストはA君のカードがC君のカードに勝てるならば0, 勝てないならば1とする.

このグラフの流量 $N$ の最小費用 $M$ を求める. これはA君がC君に勝てない試合数の最小値を求めることになる. よって答えは $N - M$ となる.