7K12 blog

猫でも分かるアルゴリズム解説

Nim

f:id:tkr987:20200202172441p:plain

「山から石を交互に取る」という文章からNimという有名なアルゴリズムだと分かる。

grundy数が0なら後手必勝、0でなければ先手必勝。

https://atcoder.jp/contests/dp/submissions/9877090

 

各山の値を排他的論理和するのが典型テクニックになるが、今回は山が1つだけの単純な問題なのでXORする必要がない。grundy数はmex(集合に含まれない最小値)を適用して計算する。Nimアルゴリズムの詳しい説明は以下のリンクが参考になるが、完全に理解しようとすると難しい気がする。

https://www.creativ.xyz/grundy-number-1065/

  • 自分の手番でgrundy数ゼロだと自分の負け
  • 石が0個のとき先手がgrundy数ゼロなので後手必勝

と暗記すれば効率良いかもしれない。

理解してなくても実用的にはテストケースと逆の答えになったら逆に出力すれば解決しそうではある。