EDPC K - Stones
石
考え方
ABCでいうと、D問題級。
対戦ゲームの問題で、
- 「こうなったら終了」のパターンが少ない
- 局面がループすることが絶対にない
という場合には、バックトレースで動的計画法をするのが有効。
つまり、勝負の決着に近い方から順に考え、以下で更新していく。
- 自分の行動後に後手必勝状態になるものが1つでもあれば、先手必勝
- 自分の行動後が後手必勝状態になるものが1つもなければ、後手必勝
計算量は $O(NK)$。
この手の問題は ABC の E 問題以降で、他のいろいろと組み合わされて出題されることも多い。
この問題が簡単と感じるくらいに慣れておきたい。
入力例3での動作
入力を受け取る。
n: 2
k: 7
a: {2, 3}石の数が少ない方から、手番側が勝てるかを決める。
$1$ 回で取れる石の数は $2$ 個か $3$ 個である。
| 石の数 | 手番側 | 理由 |
|---|---|---|
| $0$ | 負け | 石を取れない |
| $1$ | 負け | 石を取れない |
| $2$ | 勝ち | $2$ 個取ると、石が $0$ 個の負け状態になる |
| $3$ | 勝ち | $2$ 個取ると、石が $1$ 個の負け状態になる |
| $4$ | 勝ち | $3$ 個取ると、石が $1$ 個の負け状態になる |
| $5$ | 負け | $2$ 個取っても $3$ 個取っても、相手を勝ち状態にする |
| $6$ | 負け | $2$ 個取っても $3$ 個取っても、相手を勝ち状態にする |
| $7$ | 勝ち | $2$ 個取ると、石が $5$ 個の負け状態になる |
石が $7$ 個ある初期状態では手番側が勝てる。
したがって、答えは First。
注意点
特になし。
別解
特になし。