競技プログラミング総合スレ 64

競技プログラミング総 ..

949:デフォルトの名無しさん
22/12/26 19:25:08.31 TDmnxh2KM.net
さっき考えついた問題
はじめ、頂点1つの根付き木（当然その頂点が根）がある。これからN-1の頂点をこのグラフに以下の手順で一つずつ追加する：
・P/Qの確率で新たに加える頂点を根とした新たな根付き木を追加する。辺は加えない。
・1-P/Qの確率で、既にグラフに存在している頂点の一つを一様ランダムに選び、その頂点の子として新たに頂点を加える。
なお、帰納的にこのグラフは根付き木の森になる。このとき、以下の期待値を求めよ。
・根付き木の頂点数の平均値
・根付き木の頂点数の最大値
・根付き木の高さの平均値
・根付き木の高さの最大値
それぞれどの程度の制約でできるか。

次ページ

続きを表示

1を表示