Divisor Game [LeetCode 1025]

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];
	}
};