Project Euler Problems 60, 61

どちらも難問だった。

Problem 60

問題はこちら。Nまでの素数全体を頂点集合とし、2つの素数を連結してもまた素数になるときに枝があるような、無向グラフを考える。すると、このグラフの大きさ5のクリークのうち、和が最小のものを求める問題になる。
無向グラフのサイズ5のクリークを求めるのはO(n⁵)時間かかるので、N=10000=10⁴でも計算量が10²⁰くらいになって全く走らない気がしてくる。が、実際にグラフを作ってみると、N=10000では頂点数1227に対し平均次数が29.6で、かなりスパースなので走る。
ただし、サイズの5クリークを求めるときにも、単純な総当りではなく、2点 u,v を選んだら u, v の共通隣接点が3点未満の場合は枝刈りするなどの工夫が要る。
最終的なコードはこちら。クリークの探索は速いのだが、グラフの生成に時間がかかってしまった。また、答えを確定させるためN=30000に取る必要がある（答えの値だけならN=10000でも出る）。実行時間は155秒。

Problem 61

問題はこちら。今度は、4ケタの四角数〜八角数の全体を頂点とし、サイクルの辺になりうる部分に枝を引いた、有向グラフを考える。また、各頂点が何角数になりうるかを、可能な頂点の色として管理する。すると、問題は6サイクルで6彩色可能なものを求める問題になる。
有向グラフの6サイクルを求めるのはO(n⁶)かかるのだが、やはりこのグラフもスパースである。実際、頂点数351に対し平均次数は2.9しかない。
結局、グラフの6サイクルを全部求め、そのうち6彩色可能なものを調べあげることにした。最終的なコードはこちら。実行時間は1秒未満。