読者です 読者をやめる 読者になる 読者になる

Uva:11840 Tic-tac-toe

問題↓


Tic-tac-toe

問題概要

  • 横幅Nの一次元のグリッドに 'x' と '.' がいくつかあります。
  • プレイヤーは2人いて交互に'.'の場所に'x'を置くことができます。
  • 先に'x'を3つ以上並べた方の勝ちです。
  • 先行が必勝なら'S'を後攻が必勝ならば'N'を出力して下さい。

解法

  • grundy
  • 持つ情報は、[自分が置ける場所が連続していくつあるか]
  • xを置くと置いたマス左右2マスずつが置いていけない場所になる
ソースコード

感想

grundy数の勉強。

grundy数 = 遷移先のgrundy数に現れない0以上の最小の数。

grundy数dpの形はだいたい一緒なので覚えておくといいと言われた。

基本はある状態に対してgrundy数のxorを取っていく。(Nimる)