POJ 2505 A multiplication game

問題

StanとOllieが掛け算ゲームをして遊ぶ。数字を1から始めて毎ターン2から9までの好きな数字をかけていく。数字が与えられた数n以上になった時、そのときのプレーヤが勝ちとする。Stanからプレーを始めて交互に行う。両者が最適にプレーする時、必勝はどちらか答えよ。

やりかた

ゲームの木の探索。

• 今の数字から行くことのできる数字が全て相手に必勝形であれば自分はどうやっても必敗（後手必勝形）
• 今の数字から行くことのできる数字に一つでも相手が必敗になる数字があれば自分はそこに行けば勝てるので必勝（先手必勝形）

というルールでゲーム木を探索すればいい。
メモ化しないと時間が厳しかったので20000000未満の数字に限ってメモ化した。

以下ソース。

const int MAXN = 20000000;

long long N;
char memo[MAXN];
bool rec(long long p){
  if(p >= N) return false;
  if(p < MAXN && memo[p] != -1) return memo[p];
  bool a = true;
  for(int i = 2; i <= 9; i++) a &= rec(p * i);
  if(p < MAXN) memo[p] = !a;
  return !a;
}

int main(int argc, char **argv){
  while(cin >> N){
    memset(memo, -1, sizeof(memo));
    cout << (rec(1) ? "Stan" : "Ollie") << " wins." << endl;
  }
  return 0;
}