概要
V 個の頂点から成る二つの木 T1, T2 が与えられ、この二つを V 本の辺で結ぶ。
より詳しくは次の手順で辺を張る。
- 0 ? V - 1 の順列をランダムに一つ選び P とする
- 各 i ( 0 <= i < V ) について、T1[ i ] と T2[ P[ i ] ] の間に辺を張る
このとき、相異なる K ( 3 <= k <= 7 ) 個の頂点からなる長さ K の閉路の数の期待値を求めよ。
解法
まず、制約から次のことが言えます。
- 閉路に含まれる頂点が相異なることと K の制約から、長さ K の任意の閉路は木の間を丁度一回往復する。
- 木であるので、同じ木に含まれる二頂点間を結ぶパスは一本
これらから更に、次のことが言えます。
- それぞれの木から二つずつ頂点を指定すると閉路が一意に定まる
- このとき、それぞれの木についての全点間最短距離が分かっていれば、パスの内、木の中にある部分の長さが求まる
- それぞれの木についての内部でのパスの長さに 2 を足した値が、閉路全体での長さ
次に、求めたい期待値について確認します。
期待値は、事象の生起率とそのときの値を掛けたものなので、単一の閉路毎に考えると求めたい期待値は
となります。
ここで C はできる閉路の数、 はその閉路ができる確率です。
ところで、木の間を結ぶ辺について、片方の端点は固定されています。
順列によって選ばれる側の端点が、着目している閉路ができる選び方となる確率は V 個から 2 個とる順列のうちの一つなので です。
つまり、 は一定値 をとります。
従って上の式は
という形に変形され、頂点数と閉路の数だけが分かれば十分であることが分かります。
長さ K の閉路を数えたいのですが、四つの頂点の選び方を全通り試すと になって TLE します。
ところが、片方の木について二頂点を決めたとき、長さ K の閉路がいくつできるかを高速に求められれば ぐらいになって間に合います。
片方の木の内部を通るパスの内、長さが K - 端点を固定した木の内部のパスの長さ - 2 となるものの数を予め求めておくとうまくいきます。
まとめると、手順は次のようになります。
- それぞれの木について Warshall-Floyd 法で全点間最短距離を求める
- 片方の木について、内部でのパスを全通り列挙し、長さからパス総数を求められるようにする
- 他方の木について、内部でのパスを全通り列挙し、他方の木と合わせて長さ K になるものを数え上げる
- 長さ K の閉路の総数を V( V - 1 ) で割ったものが答え
コード
typedef long long LL; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; typedef istringstream ISS; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define ALL( c ) (c).begin(), (c).end() #define PB( n ) push_back( n ) const int INF = INT_MAX / 2; class TreeUnion { public: double expectedCycles( vector <string> tree1, vector <string> tree2, int K ) { VVI G1 = constract( tree1 ), G2 = constract( tree2 ); const int V = G1.size(); REP( k, 0, V ) { REP( i, 0, V ) { REP( j, 0, V ) { G1[i][j] = min( G1[i][j], G1[i][k] + G1[k][j] ); G2[i][j] = min( G2[i][j], G2[i][k] + G2[k][j] ); } } } map<int,int> paths; REP( i, 0, V ) { REP( j, 0, V ) { if ( i == j ) { continue; } paths[ G2[i][j] ]++; } } LL res = 0; REP( i, 0, V ) { REP( j, i + 1, V ) { res += paths[ K - G1[i][j] - 2 ]; } } return 1. * res / ( V * ( V - 1 ) ); } VVI constract( const VS &src ) const { VI x; { string str = accumulate( ALL( src ), string() ); ISS iss( str ); for ( int tmp; iss >> tmp; x.PB( tmp ) ); } const int V = x.size() + 1; VVI G( V, VI( V, INF ) ); REP( i, 0, V ) { G[i][i] = 0; } REP( i, 0, x.size() ) { G[ i + 1 ][ x[i] ] = G[ x[i] ][ i + 1 ] = 1; } return G; } };