SRM617Div1Medium

問題

N人のプログラマーがいる会社にM回行くことを考える。毎回AとBのおもちゃを持って行き、choice1とchoice2のプログラマーにどちらかのおもちゃを渡す。各プログラマーが持っているAとBの差分の総和が小さくなるように、どちらのプログラマーにどちらのおもちゃを与えるかを設計せよ。

解法

プログラマーをノードとして考えると、M個のエッジとN個のノードを持つグラフと考えられる。choice1にAをchoice2にBを渡すと仮定し、この関係をchoice1->choice2の向きを持つエッジとする(Aを始点、Bを終点)。入ってくるエッジの数をin、出て行くエッジの数をoutとする。
ノードの次数が偶数ならばinとoutの差分は0に、奇数ならば1にすることができる。そして、これが最適な状態となる。そのため、 $in_i - out_i \geq 2$ となるiが存在する場合、必ず $in_j - out_j \leq -1$ となるjが存在する。逆もまた同様であり、 $in_i - out_i \leq -2$ となるiが存在する場合、 $in_j - out_j \geq 1$ となるjが存在する。
iとjを探索し、その間のエッジの向きを逆向きにすることで最適な状態に近づけることができる。
iとjを見つけるのは、エッジを全探索すれば良いだけである。しかし、iとjのパスの中にjになることができるノードを含んではいけない。iから最短のjを見つけることで、この問題は解決できる。BFSを使うことでjを探索できる。