Leetcode Note: Go - Nim Game

Nim Game - LeetCode
https://leetcode.com/problems/nim-game/

• Go 言語で取り組んだメモ

所感

• nim game
• テーブルの上に石の山ガアあり、交互に交代して先に進む
• 手番で 1 - 3 個の石を取り除く
• 最後の石を取り除いた人が勝ち
• 石の数 n とした時、適切なプレイをして勝てれば true 負ければ false を返す

回答

Nim Game - LeetCode
https://leetcode.com/problems/nim-game/solution/

func canWinNim(n int) bool {
    return n % 4 != 0
}

• 4 で割り切れない場合は必ず勝てるので、それを判定すれば良い
• 小さなケースで考える
  • 石が 1 or 2 or 3 個の場合、自分の番で石を全て取れば勝てる
  • 石が 4 個の場合、どれだけ石をとっても相手が最後の石を取れるので負けてしまう
  • 勝つためには、自分の手番で石の山がちょうど4個になっている必要がある
• 大きなケースで考える
  • 石が 5 or 6 or 7 個の場合、相手が負けるように 4個 の石を残すように石を取れば勝てる
• スケールと一般化
  • n が 4, 8, 12, 16, … と 4 の倍数であれば同じパターンを繰り返すことが出来る

実装はかなり簡単だが 4 の倍数で負けるという式の構築が出来なかった・・・