唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

久しぶりにProject Eulerの問題を解いた(265, 301)

最近Project Eulerが話題になっていたので、久しぶりにやってみた
解いてる人数が多そうな問題の中から比較的問題番号の大きい物を選んで解いた。

127問解いていて、日本人の中では150位(/2470)らしい
……それにしてもいつの間にか150問解いても100位以内にすら入れなくなってるのかぁ

Binary Circles

5桁の2進数を、ある数の最後の4桁が次の数の最初の4桁と等しくなるようにつなげていって全部をつなげる
可能なすべてのつなぎ方を10進数になおした数の総和を答える

00000から始まるDe Brujin sequenceを求めるのと一緒。
De Brujin graph上でオイラー閉路ハミルトン閉路を求める問題と同じらしい

最初が00000なので最後は10000
各数の末尾4文字(16種類)について次の数の候補は2通りしかなく同じのは1回しか使えないので、大きめに見積もっても\(2^{14}\)通りぐらい。
深さ優先探索で解ける

Nim

山が3つあるNimをプレイするときに、山の数がそれぞれ(n, 2n, 3n)の場合、後手が勝てるnの個数を答える
条件を満たす数をいくつか2進数で表示させてみると、法則性が見えてくるので、あとはその法則性を満たす数を数える