torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 581, Division 1, Level 2 : TreeUnion

概要

V 個の頂点から成る二つの木 T1, T2 が与えられ、この二つを V 本の辺で結ぶ。
より詳しくは次の手順で辺を張る。

  1. 0 ? V - 1 の順列をランダムに一つ選び P とする
  2. 各 i ( 0 <= i < V ) について、T1[ i ] と T2[ P[ i ] ] の間に辺を張る

このとき、相異なる K ( 3 <= k <= 7 ) 個の頂点からなる長さ K の閉路の数の期待値を求めよ。

解法

まず、制約から次のことが言えます。

  • 閉路に含まれる頂点が相異なることと K の制約から、長さ K の任意の閉路は木の間を丁度一回往復する。
  • 木であるので、同じ木に含まれる二頂点間を結ぶパスは一本

これらから更に、次のことが言えます。

  • それぞれの木から二つずつ頂点を指定すると閉路が一意に定まる
  • このとき、それぞれの木についての全点間最短距離が分かっていれば、パスの内、木の中にある部分の長さが求まる
  • それぞれの木についての内部でのパスの長さに 2 を足した値が、閉路全体での長さ

次に、求めたい期待値について確認します。
期待値は、事象の生起率とそのときの値を掛けたものなので、単一の閉路毎に考えると求めたい期待値は
 \sum_{i=1}^C 1 \times p_i
となります。
ここで C はできる閉路の数、p_i はその閉路ができる確率です。
ところで、木の間を結ぶ辺について、片方の端点は固定されています。
順列によって選ばれる側の端点が、着目している閉路ができる選び方となる確率は V 個から 2 個とる順列のうちの一つなので \frac{1}{V( V - 1 )} です。
つまり、p_i は一定値 P = \frac{1}{V(V-1)} をとります。
従って上の式は
 \sum_{i=1}^C 1 \times P = P \sum_{i=1}^C 1 = \frac{1}{V(V-1)} \sum_{i=1}^C 1
という形に変形され、頂点数と閉路の数だけが分かれば十分であることが分かります。

長さ K の閉路を数えたいのですが、四つの頂点の選び方を全通り試すと O( V^4 )になって TLE します。
ところが、片方の木について二頂点を決めたとき、長さ K の閉路がいくつできるかを高速に求められれば O( V^2 ) ぐらいになって間に合います。
片方の木の内部を通るパスの内、長さが K - 端点を固定した木の内部のパスの長さ - 2 となるものの数を予め求めておくとうまくいきます。

まとめると、手順は次のようになります。

  1. それぞれの木について Warshall-Floyd 法で全点間最短距離を求める
  2. 片方の木について、内部でのパスを全通り列挙し、長さからパス総数を求められるようにする
  3. 他方の木について、内部でのパスを全通り列挙し、他方の木と合わせて長さ K になるものを数え上げる
  4. 長さ 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;
	}
};