Project Euler 344(2)

http://projecteuler.net/index.php?section=problems&id=344

まったく手がかりがつかめなかった。8月下旬、Project Eulerの夏休みも終わるのでそろそろこの問題を解いておこうと思い、幸い固有名詞があるのでそれで検索した。そうすると英語のページがヒットして、Nimと書いてある。蟻本を見てみると確かに同じような問題が載っている。しかし、Project Eulerいつもここからが本番なのだ。だが、このような問題はベテランならよく考えればわかるはず。最初、どう考えても計算量がO(n2)より多くなってしまったが、3日くらい考えてXORの性質を使えば速くなりそうだとわかった。要するにこれは分配の問題なのだが、2種類3つの母関数を計算すればよいのだ。しかし、コードにするのが難しく時間が取れないこともあってなかなかコードを書けないでいた。しかし、昨日今日でコード化した。しかし、ものすごく遅い。母関数の求め方が悪いのか。これを速くしたら37秒になった。よし、これで合っているはず。しかし入力するとincorrectとなった。

ジョギングにでかけて考えた。しかし、どこが悪いか思いつかない。しょうがないから剰余を取っているところを外して最後に剰余を取ることにしようと考えた。1時間あまり走って帰ってきてシャワーを浴びる前にそこを直そうとして、なぜかもう一度問題の除数を見てみた。そうしたら間違っているじゃないか。これで正解になった。62着。
やっと2か月半あまり刺さっていたとげが抜けた。これで平安な日々が送れるといいのだが。