mini notes

競技プログラミングの解法メモを残していきます。

CODE FESTIVAL 2016 Final D - Pair Cards (700)

問題:D - Pair Cards

解答:Submission #10528447 - CODE FESTIVAL 2016 Final

解法:mod Mごとに数をグループ分けする。ペアの作り方は下記の3通り。

  1. 同じ数同士でペアを作る
  2. 同じグループの違う数同士でペアを作る
  3. 異なるグループの数同士でペアを作る

グループ0とMが偶数の時のグループM / 2については1, 2の作り方のみ可能である。違う数同士でペアを作れるため、ペアの個数はグループ内の数の個数 / 2(切り捨て)となる。

グループiとグループM - iについては、1, 2, 3全てのペアの作り方が可能である。ここで、最大のペア数を生み出すペアの作り方、すなわち最大マッチングの方法は下記の通りである。(グループiの数の個数をT、グループM - iの数の個数Sとし、T ≦ Sとして一般性を失わない。)

  • T個のペアを3の作り方で作る(グループiの数は全てペアになる)。このときグループM - iの数はペアに出来ないものから選ぶ
  • グループM - iの残りのS - T個について、ペアに出来るものをペアにする

この方法で最大マッチングが実現できることを次のように証明する。

  1. 最大マッチングが与えられたとき、ペアの数を減らさずにグループiの数は全てグループM-iとペアになっているようにできることを示す
  2. 上記の場合、グループM-iの数はペアにならないものからグループiとマッチングされていることを示す

2はもしそうでなければ最大マッチングでないことがあるため、その通りである。よって1を示す。 最大マッチングが与えられたとき、グループi、グループM - i の数は下記の3通りの状態にある。

  1. ペアになっていない
  2. 同じグループの数とペアになっている
  3. 違うグループの数とペアになっている

3の場合は問題ない。

グループiに1の状態の数がある場合、グループM-iにも1の状態の数があれば、ペアが出来てしまうため、最大マッチングの仮定よりグループM-iには1の状態の数がない。T ≦ Sを仮定するため、グループM-iには2の状態の数がある。よってそのペアを解消し、グループiとグループM-iとでペアを作れればよい。

グループiに2の状態の数がある場合、まずそのペアを解消する。このときグループM-iに1の状態の数が2つ以上あると、最大マッチング以上のペアが作れてしまうため、グループM-iに1の状態の数は1以下である。このときT ≦ Sを仮定するため、グループM-iに2の状態の数がある。よってこちらもそのペアを解消し、グループiとグループM-iとでペアを作り直せばよい。