SRM 360 Div2 Hard TakeSubstringGame

問題

与えられた数nに対して二人が次のようなゲームする。

• nの、部分文字列であるような「正しい数」を選ぶ。
• nから正の「正しい数」を引く。
• その数を新たなnとして、相手のプレイヤーが同様のことを行う。
• 正しい数を取れなくなったプレイヤーの負けである。

お互いが最善を尽くすとき、先手が勝つならば、先手の選ぶべき数を（複数ある場合、最も小さいもの）返し、後手が勝つならば-1を返せ。

ただし、正しい数とは、先頭に0が来ず、なおかつ元の数自体になっていないような部分文字列を言う。

制約条件

n≦10^6

方針

メモ化再帰して探索すれば解ける。特に工夫は必要ない。
rec(n)は、nでゲームを始めたときに、先手が選ぶべき数を返す。
先手必敗の場合はinfを返す。

ソースコード

int dp[1000001];
int rec(int n){
	if(dp[n]!=-1)return dp[n];
	
	dp[n]=inf;
	
	int d[9],nd=0;
	for(int m=n;m;m/=10)d[nd++]=m%10;
	rep(i,nd)for(int j=i;j<nd;j++)if(d[j]!=0&&!(i==0&&j==nd-1)){
		//leading zeroが来ない、かつ、全体になっていないものが選択肢
		int m=0;
		for(int k=j;k>=i;k--)m*=10,m+=d[k];
		if(rec(n-m)==inf)dp[n]=min(dp[n],m);
	}
	return dp[n];
}

class TakeSubstringGame {
	public:
	int winningMove(int n) 
	{
		rep(i,n+1)dp[i]=-1;
		int ans=rec(n);
		
		return ans==inf?-1:ans;
	}
};