ゲームDP：勝ち状態を定義する
完全情報・交互手番で、合法手がなくなった人が負けるゲーム。勝ち状態は「相手を負け状態に送れる状態」です。
言語：Python / 計算量：O(N × 手の種類数)
考え方
- 手がない状態は負け。
- 1つでも負け状態への手があれば勝ち。
- 全ての手が勝ち状態へ行くなら負け。
具体例
石を1個か3個取る。0は負け、1は勝ち、2は負け、3は勝ち。手番の人を基準に状態を定義します。
実装
n=6;win=[False]*(n+1)
for x in range(1,n+1):
win[x]=any(x>=k and not win[x-k] for k in [1,3])
print(win[n])注意する条件
引き分けや閉路があるゲームは単純な小さい順DPでは解けません。独立ゲームの和にはGrundy数とxorを学びます。
確認問題
1個か3個取れる石2個の局面は先手勝ち？ Yes/No
解答と理由
No
1個取るしかなく、相手が最後の1個を取れます。
実装課題
石N個から毎手1個か3個取る。取れない側が負け。最適プレイで先手勝ちなら First、負けなら Second。0≤N≤10^6。
入力:
6
出力:
Second参考実装
n=int(input());win=[False]*(n+1)
for x in range(1,n+1):win[x]=any(x>=k and not win[x-k] for k in [1,3])
print("First" if win[n] else "Second")