K – Stones 解説 (Educational DP Contest / DP まとめコンテスト)

2020年3月10日AtCoderDP, 競プロ, ゲーム, 二人零和有限確定完全情報ゲーム, 後退解析

問題へのリンク

問題概要

二人で以下のゲームを行う。先手と後手のどちらが勝つか?

  • 以下の操作を交互に行う
    • A = \( a_1, a_2, \ldots, a_N\) の元 x を一つ選び、K 個の山から丁度 x 個取り除く
  • 先に取り除けなくなったほうが負け

制約

  • \(1 \leq N \leq 100\)
  • \(1 \leq K \leq 10^5\)
  • \(1 \leq a_1 < a_2 < \cdots < a_N \leq K\)

考え方

ゲームに関する問題です。後退解析という考え方が使えます。

後退解析とは、「ゲームの終了状態から出発して、ゲームの開始状態まで逆方向に解析していくこと」です。

具体的に考えましょう。残りが0個の時はその時の手番の人の負けです。ここから逆に考えると、

  • 残りが \(a_1\) 個の時は \(a_1\) 取り除けば勝てる
  • 残りが \(a_2\) 個の時は \(a_2\) 取り除けば勝てる
  • 残りが \(a_3\) 個の時は \(a_3\) 取り除けば勝てる
  • 残りが \(a_N\) 個の時は \(a_N\) 取り除けば勝てる

となり、1つ逆方向に戻って勝ち負けを判定することができるのです。ここからどんどんと戻りながら考えていきますが、普通にやると N 個ずつ分岐していってしまい、計算量が膨大になってしまいます。

そこで、後退解析は以下のようにDPを使うことで高速に計算することができます。

dp[ i ] := 残りが i 個の時に、その手番の人が勝てるかどうか

初期化

  • dp[ i ] := false

更新

配る dp で考えると以下のようになります。

  • dp[ i + a[ j ]] = dp[ i ] が false なら true

もらう dp で考えると以下の通りです。

  • dp[ i ] = dp[ i – a[ j ] ] に false が存在するなら true

意味的には後者のほうが分かりやすいかもしれません。相手が負けるような遷移先が存在するなら、そのように遷移するのが最善手です。

実装例