torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, Single Round Match 650, Division 2, Level 3 : TheKingsRoadsDiv2

問題概要

 正整数 h と,頂点数・辺数が共に 2^h - 1 の無向グラフが与えられる.辺の情報は 2 つの配列 a, b で与えられ,各 i に対し,2 頂点 a_i, b_i を結ぶ辺が存在する.
 このグラフから辺を 1 つ削除することによって完全二分木を得ることができるか?
 2 \leq h \leq 10

解法

 頂点数 2^h - 1N と書きます.
 h の制約から,頂点及び辺の数は 2^{10} = 1024 未満となります.1 つの辺を削除する方法も 1024 通り未満なので,辺を削除したグラフが完全二分木であるか否かをある程度高速に判定できれば,作れる全てのグラフについて判定を行うことで問題を解くことができます.
 では,与えられたグラフが高さ h - 1 の完全二分木であるかを判定する方法を考えます.グラフが高さ h - 1 の完全二分木であるとは,

  • 連結で,かつ閉路が無い(木の定義)

であることに加えて,

  • 次数が 2 の頂点が丁度 1 つ存在して,その頂点が根
  • 任意の頂点について,次数が 3 以下
  • 深さ d (根の深さを 0 とする)に対して,その深さの頂点数は 2^d
  • 任意の頂点について,0-based での深さは h 未満

といった特徴があります(もしかしたら余計なの混ざってるかも).閉路の検出は,DFS をしたとき同じ頂点を 2 度以上通るか否かで判定できます.また,その他の条件についても,DFS を根(次数 2 の頂点を根とする)から始めるようにして,深さをもちながら探索することで深さ毎の頂点数のカウントと,その他の条件の判定ができます.
 頂点数及び辺数が共に O( N ) 本のグラフの DFS なので,この DFS は O( N ) 時間でできます.辺を削除する方法は O( N ) 通りだったので,全体では O( N^2 ) 時間となります.

コード

using VI = vector< int >;
using VVI = vector< vector< int > >;

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define PB push_back

class TheKingsRoadsDiv2
{
public:
	string getAnswer( int h, vector <int> a, vector <int> b )
	{
		{
			auto f = bind( minus< int >(), _1, 1 );
			transform( ALL( a ), a.begin(), f );
			transform( ALL( b ), b.begin(), f );
		}

		const int N = ( 1 << h ) - 1;
		const int M = SZ( a );

		REP( i, M )
		{
			VVI G( N );
			REP( j, M )
			{
				if ( i == j )
				{
					continue;
				}
				G[ a[j] ].PB( b[j] );
				G[ b[j] ].PB( a[j] );
			}

			VI visited( N ), counts( h );
			iota( ALL( counts ), 0 );
			transform( ALL( counts ), counts.begin(), []( const int c ){ return 1 << c; } );

			const auto root = find_if( ALL( G ), []( const VI &es ){ return SZ( es ) == 2; } );

			if ( root != G.end()
					&& dfs( G, visited, counts, root - G.begin() )
					&& all_of( ALL( counts ), bind( equal_to< int >(), 0, _1 ) ) )
			{
				return "Correct";
			}
		}

		return "Incorrect";
	}

	bool dfs( const VVI &G, VI &visited, VI &counts, const int u, const int p = -1, const int d = 0 )
	{
		if ( 3 < SZ( G[u] ) || SZ( counts ) <= d )
		{
			return false;
		}

		visited[u] = 1;
		--counts[d];

		FOR( v, G[u] )
		{
			if ( v == p )
			{
				continue;
			}
			if ( visited[v] || !dfs( G, visited, counts, v, u, d + 1 ) )
			{
				return false;
			}
		}

		return true;
	}
};