srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

Nim

yukicoder No.7 プライムナンバーゲーム

問題 問題概要 省略 解法 grundy数をメモ化再帰で求めることにした。 grundy数の求め方だが、 grundy数は -負けの状態で0 -遷移先のGrundy数に含まれない最小の整数 なので、状態遷移先を列挙していき、最小のgrundy数を求めに行けばいい。今回の問題は、nか…

yukicoder No.361 門松ゲーム2

問題 問題概要 省略 解法 grundy数をメモ化再帰で求めることにした。 この問題は竹が分裂していくが、竹が一個の時のgrundy数をxorとるだけで、複数のゲームが合わさった状態のgrundy数を考えることができる。蟻本p284に書いてある。 grundy数の求め方だが、…

yukicoder No.153 石の山

問題 問題概要 省略 解法 grundy数をメモか再起で求めることにした。 この問題は山が分裂していくが、山が一個の時のgrundy数をxorとるだけで、複数のゲームが合わさった状態のgrundy数を考えることができる。蟻本p284に書いてある。 grundy数の求め方だが、…

yukicoder No.103 素因数ゲーム リターンズ

問題 問題概要 省略 解法 Mが与えられ、その中で、同じ素因数であれば1回以上2回まで同時に割ることができる。よって、それぞれのMの中でさらに素因数ごとに山に分ける。そうすると、それぞれの山をmod3とった値がgrundy数となる。 mmxsrup.hatenablog.com …

yukicoder No.102 トランプを奪え

問題 問題概要 省略 解法 grundy数とNimの勉強しました. 参考サイト pekempey.hatenablog.com d.hatena.ne.jp 上のサイトを参考にgrundy数を、1つの山について考えると、 残り枚数:0 1 2 3 4 5 grundy:0 1 2 3 0 1 のような関係になっている。 よって、n1,n…

yukicoder No.2 素因数ゲーム

問題 問題概要 複数山の石取りゲーム 解法 まず、素因数分解をします。そして、同じ素因数の数を数える。素因数の因数のどおしをxorで計算する。すべての素因数に対してその処理を行い、その結果が0であれば、後攻の人がかつ。この問題は必勝法が存在するの…