SRM636Div1Medium
問題
高さH、幅Wのボードが与えられる。各要素は、'.'、'#'のどちらかである。r個のうさぎが与えられ、一様ランダムに'.'となっている要素にうさぎを配置する。
うさぎを頂点とし、Xとf(X)をエッジでつなぐ。Xはうさぎの番号を示し、f(X)はXから最も近いうさぎを表す。距離が同じ場合は、より高いものを優先し、次に左側にあるものを優先する。
この時のグラフの数の期待値を求めよ。
解法
2点間でループになる()確率の総和が答えとなる。優先条件により、3点間以上でループになることはない。
2点間のループになる確率の総和が答えとなることを説明する。
まず、全体のグラフを考える。頂点r個に対してr個の無方向エッジが存在する。3点間以上でループを形成することはないので、r個のエッジの中には重複しているものが必ず1つ以上存在する。r個の頂点しかないため、重複なくr個のエッジを張るためにはどこかにループを形成しなければならないからである。
次に全体のグラフに所属するひとつのグラフに注目する。ひとつのグラフには必ず1つのエッジの重複が存在する。全く重複がない場合も、重複が2つ以上存在する場合も存在しない。重複数0が存在しない理由は全体の場合と同様である。重複数2以上が存在しない理由を背理法で説明する。重複数がk(k>1)であると仮定する。グラフの頂点数をnとするとエッジの数もnとなる。重複の数を考慮すると、n-k個のエッジでグラフを構築していることになる。ここで、頂点数nのグラフを構築するのに最低限必要なエッジの数はn-1個なので、k>2の場合ではグラフを構築できなくなってしまう。
よって、2点間でのループの数がグラフの数と等しくなることが分かる。なので、グラフの数の期待値が2点間でループになる確率の総和となる。
2点間でループとなる確率の総和はパスカルの三角形を用いることで計算できる。
計算量
