TopCoder, SRM 624, Division 2, Level 3 : GameOfSegments

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13204&rd=15857

問題概要

　N 頂点からなる凸多角形を成す点集合を使った二人ゲームをする。ゲームはターン制で進行し、各ターンでプレイヤーは以下のいずれかの行動の内一つを選択する。

• 多角形の対角線に線分を引く
• 多角形の辺に線分を引く

ただし、過去に双方のプレイヤーによって引かれた線分に（端点を含め）接する線分を引くことはできない。線分を引けなくなったプレイヤーは敗北となる。
　両者が最善を尽くすとき、どちらのプレイヤーが勝つか、求めよ。

解法

　部分問題として現れる問題の点の数を n と書きます。
　まず、それぞれの動きについて考察をします。

対角線に線分を引く場合

　対角線に線分を引いたとき、点集合は線分によって二つの集合に分けられます。分けられた二つの集合を横断するような線分を引くと今引いた線分に接してしまうので、以降、この二つの点集合は関係が無くなります。
　線分の片方の端点にする頂点を 0 として、時計回りに 1, 2, ... n - 1 と番号付けたとします。このとき、もう片方の端点の番号が i だとすると、i の左側（反時計回り的な意味で）に残る点の数は i - 1 です。m = i - 1 とすれば、右側に残る点の数は、N から対角線によって消える分と m を引いた数なので n - m - 2 です。また、分割されたそれぞれの点集合も凸多角形の頂点となっています。従って、元の状態と点の数だけが違う同一の問題が二つ出てくることになります。

辺上に線分を引く場合

　辺上に線分を引く場合は、二つの点がゲームから除外され、残った点が凸多角形を成します。こちらの場合、点の数が n - 2 に変化した同じ問題が出てきます。

　点集合は頂点数のみによって完全に表現されることを考慮にいれると、これは山が分裂するタイプの「Nim っぽいゲーム」であると考えることができます。従って、各状態（点の数）に対して Grundy 数を計算すれば、Nim に帰着できます。
　点を（対角線によって）分割したときのそれぞれの点の数を a, b とすれば、山が増えた状態の Grundy 数は g( a ) XOR g( b ) です（ただし g は Grundy 数を返す関数）。一方、辺上に線分を引いた場合は点の数が減るだけなので、操作後の Grundy 数は g( n - 2 ) となります。
　状態の遷移と遷移先の Grundy 数の計算方法もこれで明らかとなったので、あとは g( N ) を計算すれば、それが非ゼロならば先攻の勝利、そうでなければ後攻の勝利と問題の答えが求まります。

コード

using VI = vector<int>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

class GameOfSegments
{
public:
	VI dp;

	int winner(int N)
	{
		dp = VI( N + 1, -1 );
		return 2 - !!grundy( N );
	}

	int grundy( const int N )
	{
		if ( dp[N] != -1 )
		{
			return dp[N];
		}

		set<int> S;
		if ( 2 <= N )
		{
			S.insert( grundy( N - 2 ) );
		}
		REP( i, 2, N - 1 )
		{
			const int m = ( i - 1 );
			S.insert( grundy( m ) ^ grundy( N - m - 2 ) );
		}

		int res = 0;
		while ( EXIST( S, res ) )
		{
			res++;
		}
		return dp[N] = res;
	}
};