N個のマッチの山がある。
ここから以下の操作を順番に繰り返す。
1. マッチが1つもないなら負け
2. 1つの山を選び、1つ以上とる
3. 取ったマッチ1つにつき、1つの山を全て燃やすことができる（取った山を燃やしてもいい）
4. 使わなかった取ったマッチは捨てる（1本も使わなくてもいい）
先手が勝つなら"Yvonne", 後攻が勝つなら"Zera"
山の数≦9
各マッチの本数≦1000
解説
自分自身はACできなかったが、方針はわかったので備忘として残す。
気づくべきことがまずある。
「マッチの本数が8以上の山があれば、その山を取って他の全ての山を燃やすことで先手が勝てる」
これに気づけば、各山の本数は7本以下の状態だけを考えればいいと分かる。
これでまずは概算8^9通りくらいなので、まだ扱えそうな状態数である。
あとは、自明で先手が勝てるパターンやソートしたときに同一のものを消していくと、状態はもっと減らせそう。
状態数が収まる感じなので、バックトラックで答えを導いていこう。
遷移を書くのがとても大変で、自分も挫折したので、みなさんも頑張ってほしい。
あとは、計算量が心配なので、上位陣を見習って、負け状態をメモ化して答えよう。
