DPまとめコンテスト/K - Stones - 競技プログラミング用 知識集積所【7/12更新】

---

問題

DP-K

必要知識

ABCのB以下レベルの内容は省略

• 動的計画法
• バックトレース

考え方

ゲームっぽい問題で、

• 「こうなったら終了」のパターンが少ない
• 局面がループすることが絶対にない

という場合には、バックトレースで動的計画法をするのが有効。

例えば入力例3の場合。

• 石の数が0個の場合、後手勝ち状態で返す選択肢がないので、後手の勝ち
• 石の数が1個の場合、後手勝ち状態で返す選択肢がないので、後手の勝ち
• 石の数が2個の場合、後手勝ち状態で返す選択肢（2個取る）があるので、先手の勝ち
• 石の数が3個の場合、後手勝ち状態で返す選択肢（2個取る）があるので、先手の勝ち
• 石の数が4個の場合、後手勝ち状態で返す選択肢（3個取る）があるので、先手の勝ち
• 石の数が5個の場合、後手勝ち状態で返す選択肢がないので、後手の勝ち
• 石の数が6個の場合、後手勝ち状態で返す選択肢がないので、後手の勝ち
• 石の数が7個の場合、後手勝ち状態で返す選択肢（2個取る）があるので、先手の勝ち

と考えていくことができる。

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

解答例

解答例

注意点

別解