TopCoder, SRM 627, Division 1, Level 2 : GraphInversions

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13275&rd=16008

問題概要

　 頂点からなる無向・重み無しで連結なグラフが与えられる。辺の数は に等しく。 番目の辺は と を結んでいる。更に、各頂点には（頂点番号とは別に）整数値が割り振られていて、 番の頂点に振られた値は である。
　このグラフ上の単純道について、通過した頂点に割り振られている値を通過した順番に連結した列を考える。長さ 以上のパスの内、得られる列の転倒数が最小のものを求め、その転倒数を返せ。

解法

　 の最大値を と書きます。
　まず、与えられるグラフの形状は、木に 1 本だけ辺を追加した形、すなわち、1 つの閉路があって、その閉路から 0 本以上の木が生えている形になります。また、このグラフ上の任意の相異なる頂点 を選んだとき、 から への単純道は高々 2 通りしかありません（同じ頂点を 2 回以上通れないことと、分岐できるのは閉路を通るときにどっち向きに回るかを選択する場合だけなので）。従って、ある頂点を始点とする単純道の数は 個となります。このことから、単純道の総数は 個なので、DFS でパスを列挙しながら、ある程度高速に転倒数計算できれば問題を解けそうだということが分かります。
　ところで、長さが 、出現する値の種類が である列の転倒数の計算は、Fenwick Tree を用いて 時間でできます（蟻本参照）。更に言うと、列の中途まで処理した状態の Fenwick Tree と、その時点までの転倒数が分かっていれば、次の要素を付け加えたときの転倒数の変化分は で計算できます。これを先程の DFS に当てはめると、構成途中の単純道に次の頂点を付け加えたときの転倒数の変化は で計算できます。単純道の総数は なので、全体では となります（なお、visited の管理は単純な配列を使うことで です）。

コード

using VI = vector<int>;
using VVI = vector<VI>;
template < typename T = int > using LIM = numeric_limits<T>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

constexpr int INF = LIM<>::max();

// Fenwick Tree ( Binary Indexed Tree )
class FenwickTree ;
// FenwickTree( array size )
// int sum( 0-indexed pos )
// int add( 0-indexed pos, value )

class GraphInversions
{
public:
	int N, K;
	VVI G;
	VI V;

	int res;

	int getMinimumInversions( vector <int> A, vector <int> B, vector <int> V, int K )
	{
		{ // initilization
			this->N = A.size();
			this->K = K;

			G = VVI( N );
			REP( i, 0, N )
			{
				G[ A[i] ].PB( B[i] );
				G[ B[i] ].PB( A[i] );
			}

			this->V = V;

			res = INF;
		}

		REP( i, 0, N )
		{
			VI visited( N );
			FenwickTree bit( 1001 );
			dfs( visited, bit, i, 0 );
		}
		return res == INF ? -1 : res;
	}

	void dfs( VI &visited, FenwickTree &bit, const int u, const int inv )
	{
		if ( visited[u] )
		{
			return;
		}

		visited[u] = true;
		bit.add( V[u], 1 );

		const int d = bit.sum( 1000 ) - bit.sum( V[u] );
		if ( K <= bit.sum( 1000 ) )
		{
			res = min( res, inv + d );
		}

		FOR( v, G[u] )
		{
			dfs( visited, bit, v, inv + d );
		}
		visited[u] = false;
		bit.add( V[u], -1 );

		return;
	}
};