EDPC K - Stones

石

考え方

ABCでいうと、D問題級。

対戦ゲームの問題で、

という場合には、バックトレースで動的計画法をするのが有効。
つまり、勝負の決着に近い方から順に考え、以下で更新していく。

計算量は $O(NK)$。

この手の問題は ABC の E 問題以降で、他のいろいろと組み合わされて出題されることも多い。
この問題が簡単と感じるくらいに慣れておきたい。

入力を受け取る。

n: 2
k: 7
a: {2, 3}

dp[i] を、石が i 個ある状態が先手必勝かどうかとする。

最初は、全て後手必勝として初期化されている。

dp: {false, false, false, false, false, false, false, false}

石の数が $0$ 個の場合、返す選択肢がないので、後手の勝ちである。

dp[0]: false

石の数が $1$ 個の場合も、返す選択肢がないので、後手の勝ちである。

dp[1]: false

石の数が $2$ 個の場合、石を $2$ 個取れば dp[0] の状態にできる。
これは後手勝ち状態で返す選択肢なので、先手の勝ちである。

dp[2]: true

石の数が $3$ 個の場合、石を $2$ 個取れば dp[1] の状態にできる。
これは後手勝ち状態で返す選択肢なので、先手の勝ちである。

dp[3]: true

石の数が $4$ 個の場合、石を $3$ 個取れば dp[1] の状態にできる。
これは後手勝ち状態で返す選択肢なので、先手の勝ちである。

dp[4]: true

石の数が $5$ 個の場合、石を $2$ 個取っても dp[3]、石を $3$ 個取っても dp[2] の状態になる。
どちらも先手勝ち状態なので、後手の勝ちである。

dp[5]: false

石の数が $6$ 個の場合、石を $2$ 個取っても dp[4]、石を $3$ 個取っても dp[3] の状態になる。
どちらも先手勝ち状態なので、後手の勝ちである。

dp[6]: false

石の数が $7$ 個の場合、石を $2$ 個取れば dp[5] の状態にできる。
これは後手勝ち状態で返す選択肢なので、先手の勝ちである。

dp[7]: true

最終的に、DP テーブルは次のようになる。

dp: {false, false, true, true, true, false, false, true}

dp[7] は true なので、答えは First。

特になし。

特になし。