can-i-win.cpp (2191B)
1 class Solution { 2 public: 3 4 bool solve(bitset<21> bs, int score, bool firstTurn, int maxChoice, int target, unordered_map<long long,bool>& memo) { 5 6 if(target == 0) { 7 return true; 8 } 9 if(score >= target) { 10 return !firstTurn; 11 } 12 long long key = (bs.to_ulong() << 43); 13 key += (((long long)target) << 11); 14 key += firstTurn; 15 16 if(memo.contains(key)) { 17 return memo[key]; 18 } 19 20 for(int i = 1; i <= maxChoice; ++i) { 21 if(bs[i] == 1) { 22 bitset<21> bsc = bs; 23 bsc[i] = 0; 24 bool next = solve(bsc, score+i, !firstTurn, maxChoice, target, memo); 25 if(firstTurn && next) { 26 memo[key] = true; 27 return true; 28 } 29 if(!next && !firstTurn) { 30 memo[key] = false; 31 return false; 32 } 33 } 34 } 35 memo[key] = !firstTurn; 36 return !firstTurn; 37 } 38 39 bool canIWin(int maxChoosableInteger, int desiredTotal) { 40 // first to reach or exceed total wins 41 // no reuse 42 // true means first person can win 43 44 // what's optimal play? 45 // there's always minimax, but that'd be a bit surprising for this problem / mediume / time constrained 46 // also quite expensive 47 48 // do I run it up? 49 // do I run it down? 50 // 1 <= maxChoosableInteger <= 20 51 // 0 <= desiredTotal <= 300 52 53 // small problem space 54 // dp state := s(bitmask, currentScore, turn) 55 // bitmask has 2**20 states, currentScore has 301 possible states, turn has two stated 56 // 2**20 * 301 * 2 57 // 631_242_752 58 bitset<21> bs {}; 59 for(int i = 1; i <= maxChoosableInteger; ++i) { 60 bs[i] = 1; 61 } 62 63 unordered_map<long long,bool> memo {}; 64 if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false; 65 return solve(bs,0,true, maxChoosableInteger, desiredTotal, memo); 66 } 67 };