https://leetcode.com/contest/weekly-contest-132/problems/divisor-game/
AliceとBobがいる。
最初に数Nが書いてある。
順番に「書いてある数Nの約数dを1つ選び、N-dに書き換える。x=1でターンが来たら負け」をする。
Aliceが勝つならtrue, Bobが勝つならfalse
N≦10^3
前提知識
解説
https://leetcode.com/contest/weekly-contest-132/submissions/detail/222245972/
バックトラックで解く。
「遷移先の状態が全て、勝ち状態であればその状態は負け状態」
「遷移先の状態に負け状態が含まれれば、その状態に遷移させればいいので勝ち状態」
の原則で「dp[n] := 数nが書いてある状態が勝ち状態か」を下から埋めていけばいい。
class Solution { public: bool divisorGame(int N) { vector<int> dp(N + 1); dp[0] = 0; dp[1] = 0; rep(i, 2, N + 1) { auto ed = enumdiv(i); fore(d, ed) if (d < i) if (dp[i-d] == 0) dp[i] = 1; } return 0 < dp[N]; } };