TopCoder SRM 566, Division 1, Level 1 : PenguinSledding

概要

グラフの頂点数と辺の情報が与えられる。
「このグラフを二次元平面上にどのように配置しても辺が交差しない」ような辺の選び方の総数を答えよ。

解法

辺の選び方のパターンは以下の二通りです。

• ある頂点を起点に、それに接続する辺を選ぶ
• 三角形になるように辺を三本選ぶ

一つ目のパターンは、ある頂点に繋がる辺の総数を a とすると、 だけ存在します。
ただし、このまま実装すると辺を一本だけ使うパターンと一本も使わないパターンを重複して数え上げてしまうので、除外した方が楽だと思います。
（最初から辺の数 + 1 を足しておいて、頂点毎に a + 1 を減じて数え上げる）
２つ目のパターンについては、 などで全探索します。

コード

typedef long long LL;
typedef pair<int,int> PII;

#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 )
#define MP( a, b ) make_pair( ( a ), ( b ) )

class PenguinSledding
{
public:
	long long countDesigns( int numCheckpoints, vector <int> checkpoint1, vector <int> checkpoint2 )
	{
		const int N = checkpoint1.size();

		vector< LL > nodes( numCheckpoints );
		vector< PII > edge;

		REP( i, 0, N )
		{
			nodes[ checkpoint1[i] - 1 ]++;
			nodes[ checkpoint2[i] - 1 ]++;

			edge.PB( MP( checkpoint1[i] - 1, checkpoint2[i] - 1 ) );
			edge.PB( MP( checkpoint2[i] - 1, checkpoint1[i] - 1 ) );
		}

		sort( ALL( edge ) );

		LL res = 1 + N;

		REP( i, 0, nodes.size() )
		{
			if ( nodes[i] < 2 )
			{
				continue;
			}
			
			res += ( 1LL << nodes[i] ) - nodes[i] - 1;
		}

		REP( i, 0, numCheckpoints )
		{
			REP( j, i + 1, numCheckpoints )
			{
				REP( k, j + 1, numCheckpoints )
				{
					res += ( binary_search( ALL( edge ), MP( i, j ) ) &&
						binary_search( ALL( edge ), MP( j, k ) ) &&
						binary_search( ALL( edge ), MP( k, i ) ) );
				}
			}
		}

		return res;
	}
};