AOJ 1230 : Nim

問題リンク:Nim | Aizu Online Judge

解法：

実際にゲーム木をみていく
memo[i][j] := 人i に山の残りがjの状態できたときの勝敗
としてメモ化した
自分のチーム基準で結果のブール型をリターンする
山が残り１枚以下になった時、
　自分のチームのターンなら return false; <= 負け
相手のチームのターンなら return true ; <= 勝ち

ループで山を１枚から指定された枚数まで全て試す
　自分のチームのターンなら、リターンされた結果に１つでもtrue(勝利)があれば return true
相手のチームのターンなら、リターンされた結果に１つでもfalse(負け)があれば return false

コードーーーーーーーー

int n,S;
short M[21];
short memo[21][MAX];
 
bool dfs(int phase,int nS)
{
  if(memo[phase%(2*n)][nS] != -1)return memo[phase%(2*n)][nS];
  if(nS <= 1)
    {
      if(phase%2)return 1;//enemy
      else       return 0;//friend
    }
 
  bool res,update;
  update = false;
  REP(i,1,M[phase%(2*n)]+1)
    {
      bool bres = dfs(phase+1,nS-i);
      if(phase%2)
    {
      if(!update)
        {
          update = true;
          res = bres;
        } 
      else res &= bres; 
    }
      else
    {
      if(!update)
        {
          update = true;
          res = bres;
        }
      else res |= bres;
    }
    }
  return memo[phase%(2*n)][nS] = res;
}
 
int main()
{
  while(cin >> n,n)
    {
      cin >> S;
      rep(i,2*n)cin >> M[i];
      rep(i,21)rep(j,MAX)memo[i][j] = -1;
      //cout << "---------" <<endl;
      cout << (dfs(0,S)?1:0) << endl;
    }
  return 0;
}