C. Number Game

• Quiz
  • https://codeforces.com/problemset/problem/1370/C
• AC
  • https://codeforces.com/contest/1370/submission/88162228
• 解説
  • 想定解(editorial)と違うので書いておく
  • 相手に負け確定の状態で渡すことができるなら勝ち、そうでないなら負け
  • これをメモ化再帰で書く

map<ll, bool> mp; // memo

bool can_win(ll n){
  if(n==1) return false; // 1がきたら負け
  if(n==2) return true; // 1を押し付けられるのでWin
  if(n==3) return true; // 1を押し付けられるのでWin
  if(mp.count(n)!=0) return mp[n];

  auto Y = calc_devisors(n); // nの約数一覧
  for(ll y : Y){
    if(y==1) continue;
    if(y%2==0) continue;
    if(can_win(n/y)==false){ // 負けを押し付けることができる
      return mp[n] = true;
    }
  }
  if(can_win(n-1)==false){
    return mp[n]=true;
  }else{
    return mp[n]=false;
  }
}