grundy number

grundy numberっていうものがありまして。

以前から知ってはいたのだけど実装(=プログラムを書く)に

使えるほどには理解できてなくて。

この休み、ちょこちょこーと調べたりしてみて、

なんとなく理解した気になってたのだけど、下の問題が全然解けなくて。

あー、、やっぱまだ理解できてないんだーとか思ってたら、

やっと解けましたー、、めちゃ嬉しいw

http://acm.pku.edu.cn/JudgeOnline/problem?id=3537

問題自体はものすごく簡単です。

"n個の升目が一列にならんでいます。
AさんとBさんが交互に、好きな升に１つ。×をつけていきます。
×を3つ連続させた人が勝ち"ってゲーム。

これはn(つまり升目の数)が決まると、Aさん必勝かBさん必勝か分かるのです。

んでまぁこれはgrundy numberとかいう素敵なものを使うと

非常にあっさり解けてしまって…まぁ詳細は書きませんが。

grundy numberを勉強しようという方はこちら。

なんか今までこういう問題って"難しい"っていうイメージがあったけど、

grundy number使うと偉く簡単にできてしまうのですよ。

んー、、知識を蓄えるって大事なことだなぁ・・・