JAG夏合宿Day3-G(AOJ2994): Toss Cut Tree

こういうやつの定跡を知っているかが重要そう。

問題

onlinejudge.u-aizu.ac.jp

解法

　木から頂点を取り除いていくので、森を扱うことになる。森の連結成分の数は、頂点の数から辺の数を引いたものである。これは期待値にしても変わらず(期待値の線形性)、 $(頂点の期待値)-(辺数の期待値)$ を考えてよい。森 $T$ の最終的な頂点数、辺数に対応する確率変数をそれぞれ $v _ T , e _ T$ とし、 $U$ についても同様に定義すれば、求めるべき値は以下のように書ける。

$E[XY] = E[(v _ T - e _ T)(v _ U - e _ U)] = E[v _ T v _ U] - E[v _ T e _ U] - E[e _ T v _ U] + E[e _ T e _ U]$

この各項を計算していこう。

$E[v _ T v _ U$ ]

　 $T$ の頂点 $i$ に対し、最終的に $i$ が残れば1、消えていれば0を取るような確率変数を $X _ i$ とする。また、 $U$ の頂点 $j$ に対し、最終的に $j$ が残れば1、消えていれば0を取るような確率変数を $Y _ j$ とする。このとき、期待値の線形性から、以下のような計算ができる。

$E[v _ T v _ U] = E\left[\left(\sum _ {i=1} ^ {N} X _ i \right) \left(\sum _ {j=1} ^ {N} Y _ j \right)\right] = \sum _ {i,j} E[X _ i Y _ j]$

ここで、 $E[X _ i Y _ j$ ]は $i \neq j$ のとき $\frac {1} {4}$ で、そうでないとき $0$ である。 $i \neq j$ となる $(i,j)$ の組は $N*(N-1)$ 個あるから

$E[v _ T v _ U] = \frac{1}{4}N(N-1)$

がわかった。

$E[e _ T v _ U$ ]

　上の議論がわかれば、実はほとんと同じである。辺 $(a _ i, b _ i)$ が残るには、頂点 $a _ i, b _ i$ がどちらも残る必要がある。従って期待値の線形性より以下の等式が成り立つ。

$E[e _ T v _ U] = \sum _ {i,j} E[X _ {a _ i} X _ {b _ i} Y _ {j}]$

$E[X _ {a _ i} X _ {b _ i} Y _ {j}$ ]は $(a _ i, b _ i, j)$ がすべて異なるとき $\frac{1}{8}$ で、それ以外のとき $0$ である。よって、 $(a _ i, b _ i, j)$ がすべて異なるような $(i,j)$ の組を数えればよく、これは $T$ の各頂点の次数を持っておくことで可能である。

$E[v _ T e _ U$ ]

　これは $E[e _ T v _ U$ ]と同様なので省略。

$E[e _ T e _ U$ ]

　もはやこれも説明不要かもしれない。今までと同様に以下の等式が成り立つ。

$E[e _ T e _ U] = \sum _ {i,j} E[X _ {a _ i} X _ {b _ i} Y _ {c _ j} Y _ {d _ j}]$

$E[X _ {a _ i} X _ {b _ i} Y _ {c _ j} Y _ {d _ j}$ ]は、 $a _ i, b _ i,c _ j,d _ j$ がすべて異なれば $\frac{1}{16}$ 、そうでなければ $0$ である。 $a _ i, b _ i,c _ j,d _ j$ がすべて異なるような $(i,j)$ の組の数は、 $T,U$ の各頂点の次数を見れば計算できる。

上で述べた計算すべき値はすべて $O(N)$ で計算可能なので、この問題が $O(N)$ で解けた。

実装

特に難しいところはない。

onlinejudge.u-aizu.ac.jp