Project Euler日記 41-50

そろそろ頭がいる

41. mod 3で上限を評価したあと、順列吐かせて素数判定。こんなので頭を使ってはいけない。

note.nkmk.me

42. 虚無。題意を読み間違えてまくったので、ぼくは虚無未満の人間です。

43. 脊髄反射順列生成マン

44. いまいち釈然としない。差が小さいけど和はとんでもなく大きい、みたいなケースを消しきれず、しかたなく小さいケースで調べて投げたら通ってしまった。ちゃんと証明するなら式をいじるしかないのだろうか。うーむ。

45. 問題44でもそうだが、五角数とか六角数とかの判定は、n になりそうな数を計算してから一致するか確かめると O(1) でできる。いままで判定リストを作ってバケツっぽく調べていたが、これだといろいろ不都合なく調べられそう。あとは三角数をしたから列挙すればOK. 

ところでこういう数って無限にあるんですかね。2 種類だとペル的に無限にありそうだけど、3 種類だと不明すぎる。一般のほげ角数への理解が足りない...

46. 意外と小さかった。過去の人々、探索力足りてなくな〜い?(言いがかり)

47. けっこう探索時間がかかった。Pythonで 1 分だと 10^9 くらいの計算時間が目安かなぁ。

48. なんでこの問題だけ解かれてるんや、みんなこんな問題好きなんやね〜

... と思って考えたら、ただ簡単なだけだったというオチ。mod 1e10 です。最初ビック数DPメソッドしようとしててアホだった。O(N logN) でできるけど、頭がついてなかったので O(N^2) です。

49. 4 桁の素数は 1000 個くらい。その二乗くらいの計算量。だんだんこういう計算量を意識する必要が出てきた。

50. 累積和って知ってますか?知ってたとしても、現実的な計算量にするために少し工夫した方がよさそう。

 

これで Level 2 になりました。いぇい。

虚無ゾーンを抜けたっぽい。こっからが本番。