人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

Educational DP Contest:K - Stones

問題

atcoder.jp

解法

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).

解答

atcoder.jp

「相手を負けにする ⇔ 自分を勝ちにする」を利用する.

f:id:babcs2035:20190107171457p:plain