きままにものづくり

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

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を探索できる。

計算量

iとjの探索回数

エッジの数はMなので、最大の次数はMとなる。一回の反転で必ず1減らせるので、計算量はO(M)となる。

BFS

iをルートとするツリーを持っていないので、毎回エッジを探索する必要がある。jの深さをDとすると、計算量はO(DM)となる。深さは最大でN-1になる。

全体の計算量

計算量:  O(N M^2)
(i,j)の探索回数: O(M)
BFS: O(NM)

コード