TopCoder SRM 575, Division 2, Level 2 : TheNumberGameDivTwo

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12497&rd=15495

概要

二人で、数字を使ったゲームをする。
ゲームでは、交互に手番が回り、自分の手番では以下の操作をする。

1. 現在の値を C として、1 と C 以外の C の約数を一つ選ぶ（ ここでは d とする）
2. C - d を次の値として、相手の手番とする

操作ができなくなったプレイヤーは敗北する。
C の初期値 n が与えられるので、お互いが最適な戦略をとるとき、どちらのプレイヤーが勝利するか求めよ。

解法

敗北条件を確認しておくと、C が素数になれば負けます。
このゲームで Grundy 数を計算すると、C が素数ならば遷移できないので Grundy 数は 0 になります。
Grundy 数が 0 となる、素数ではない状態からは遷移が可能で、Grandy 数は増加します。
しかし、Grundy 数の定義より、Grundy 数が g の状態からは、Grundy 数が 0 〜 g - 1 の全ての状態に遷移できます。
つまり、次の相手の一手で Grundy 数が 0 の状態に戻されてしまいます。
そしていつかは C が素数であるような Grundy 数が 0 の状態にされてしまいます。
従って、最初の状態で Grundy 数が 0 だと負けてしまいます。
逆に、最初の状態で Grundy 数が 0 でなければ、相手に Grundy 数が 0 の状態を回すことができるので、勝つことができます。

コード

typedef vector<int> VI;

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

class TheNumberGameDivTwo
{
public:
	VI dp;

	string find( int n )
	{
		dp.resize( n + 1, -1 );
		return grundy( n ) ? "John" : "Brus";
	}

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

		set<int> s;
		REP( d, 2, x )
		{
			if ( !( x % d ) )
			{
				s.insert( grundy( x - d ) );
			}
		}

		int g = 0;
		while ( EXIST( s, g ) )
		{
			g++;
		}

		return dp[x] = g;
	}
};