ABC149 - F - Surrounded Nodes - Senの競技プログラミング備忘録

atcoder.jp

概要

サイズNの木が与えられる。それぞれの頂点を1/2の確率で白、1/2の確率で黒と塗る。
黒で塗られた頂点をすべて含む最小部分木を考える。その最小部分木のサイズの期待値を求めよ。

制約： 1 <= N <= 2 * 10^5

ACするまで

1. 期待値だ・・・。木の上をDPでやってみようかな。
2. DPでやるなら、部分木に入ってるか？とかの情報も添え字に必要。つらい。
3. 端点じゃなかったらよさそうだな。非端点の頂点に着目する。
4. コンテスト終了

5. 期待値の線形性を使うと、非端点の頂点ごとの期待値の総和になる。
6. 頂点ごとに着目すれば、下述の数式で求まる期待値が求まる。集計すればよい。
7. AC

考察

この問題は解説を見る限り、2通り以上の解法がある。

頂点に着目
辺に着目

の3つについて書く。(全方位木DPは追記する。ひとまず２つ)

頂点に着目

期待値の問題では、遷移図が書けるタイプ(コインを数回投げて、何回連続の期待値とか、ランダムウォークの期待値とか。基本的に立式して、連立方程式を解く)と、大学受験の場合の数的に計算するタイプ(正確には、前者に入らない)の2つに基本的に分けられると思う。

今回の問題で、前者だと仮定してDPテーブルを書いてみると、添え字の情報に、
dp[今いる頂点][今の頂点の色][白ならば、何個連続で白が続いて穴あきがあるか]
のように持たせることが必要だと思う。しかし、これは明らかにメモリ的にも、計算量的にもとてもできたことではない。

では、大学受験数学のアプローチのように考えてみる。

まず、期待値の線形性に絡められるか？を考えてみる。
期待値の線形性は「○○を満たすものの期待値＝○○をいくつかに分割して、それらの分割されたものの期待値を足し合わせたもの」という性質を持つ(線形性はもっと強力な性質であり、これはより具体化したもの)。非常に強い性質として、○○の各部分がお互いに独立でないものでもなりたっちゃうのである。

以下の記事は期待値に詳しい。期待値の考え方に早く慣れることがAtcoder問題ACの貴重なポイントであると思う。
qiita.com

さて、今回の場合、「部分木の穴あき度の期待値」である。穴あき度は、頂点ごとに＋１もしくはなにもないで、木は頂点によって構成されるので、この命題の細分化の単位を「各頂点ごとの、穴あき度の期待値」とできる。この場合は、各頂点ごとに穴あき度として加算されるかは全く持って独立ではないけど、期待値の線形性は独立でなくても成り立つ素晴らしい性質なので、このように分割できる。

一般的に、木についての期待値は、木は頂点と辺によって構成されるといえるので、これらを単位に分割するの、典型テクニックである。(要出典、僕は今そう思ってる)

さて、ここで問題は、「ある頂点Xによって、加算される穴あき度の期待値」を求める問題に言い換えられた。

ここからは大学受験の場合の数の領域である。
まず、穴あき度を加算される前提条件として、「今着目してる頂点が白く塗られること」である。この事象の確率は $\frac{1}{2}$ 。また、穴あき度は加算されるのなら+1、そうでない場合は0なので、この事象の期待値は同じように $\frac{1}{2}*1=\frac{1}{2}$ である。
次に、白く塗られても穴あきにならないのはどの場合かを考える。すると、部分木に入らないと穴あきにならないので、それを考える。

そもそも端点、端っこの点。白くなったところで部分木には入れない。
端点でなくとも、自分以外の頂点がすべて白で塗られたら、そもそも部分木が存在しないので論外。
端点でなくとも、自分から出てる枝の先で、1つの枝の先にしか黒が存在しない。その枝の先で部分木が終わっていて、着目してる頂点まで伸びることはないため。

逆に、この3つ以外ならば、木という性質上、2つ以上の枝の先で黒が存在するのならば、それらをつなげるために今着目してる頂点を必ず通るので、穴あき度としてカウントされる。

これを数式にしてみる。考察の中で見られる2つ以上の以上のワードから、余事象のにおいがぷんぷんする。実際、着目してる頂点が白であるときの穴あき度に含まれる条件付き期待値は、
1-(自分以外すべて白く塗られてる)-(1つの枝の先にしか黒が存在しない)
である。(包除原理)

後はこれを計算すればよい。
自分以外すべて白く塗られてるは、条件付き期待値として $\frac{1}{2^{N-1}}$ である。
1つの枝の先にしか黒がないのは、自分から出てるすべての枝とその先につながる部分木のサイズをDFSで前計算(やり方は後述)しておいて、黒にする枝の先を全部試して引けばよい。これをやると、 $\sum_{i=1}^{出てる辺の数}(\frac{1}{2^{N-1-{q_i}}}*(1-(\frac{1}{2^{q_i}})))　ただし、q_iは今着目してる枝の先の頂点数$
これらから、「ある頂点Xによって、加算される穴あき度の期待値」がわかるので、すべての頂点に対してこれを計算して、足し合わせればよい。

ちなみに、DFSで各頂点から出てる辺の先のそれぞれの頂点数を求めるには、
1. 何かしらの頂点を根とする。
2. それぞれの頂点にdp[i] := 頂点iを根とした部分木のサイズ、Tree[i][j] := 頂点iから出てるj番目の辺の先の頂点数　と定める。
3. 1で定めた頂点からDFSする。DFSしながら、下記のソースコードのように、いい感じにdpとTreeを同時に更新する。
4. 最後に頂点iの親に当たる頂点方向の部分木のサイズを計算する。これは、N-1(自分のぶん)-(自分の子供の部分木のサイズの和)で求めることができる。

以下のソースコードでは、自作のModintライブラリを使用した。コピペしてかまいません。

ACソースコード：

Submission #9240645 - AtCoder Beginner Contest 149