Uva:11840 Tic-tac-toe
問題↓
問題概要
- 横幅Nの一次元のグリッドに 'x' と '.' がいくつかあります。
- プレイヤーは２人いて交互に'.'の場所に'x'を置くことができます。
- 先に'x'を3つ以上並べた方の勝ちです。
- 先行が必勝なら'S'を後攻が必勝ならば'N'を出力して下さい。
解法
- grundy数
- 持つ情報は、[自分が置ける場所が連続していくつあるか]
- xを置くと置いたマス左右2マスずつが置いていけない場所になる
ソースコード
感想
grundy数の勉強。
grundy数 = 遷移先のgrundy数に現れない0以上の最小の数。
grundy数dpの形はだいたい一緒なので覚えておくといいと言われた。
基本はある状態に対してgrundy数のxorを取っていく。(Nimる）
