Educational DP Contest:K - Stones
問題
解法
dp(i, j) := 石が i 個あり操作するのが j のとき,j が勝てるかどうか
と定義する.このとき,残りの石の状態のうちどれかが相手を負けにすることが出来るならば,自分を勝ちにできることを踏まえると,
dp(i, j) = !dp(i - a_1, (j + 1) % 2) OR !dp(i - a_2, (j + 1) % 2) OR ... !dp(i - a_k, (j + 1) % 2) (a_k <= j)
と漸化式が立つ.状態数 O(K),遷移 O(N) になり O(NK).
解答
「相手を負けにする ⇔ 自分を勝ちにする」を利用する.