Project Euler 345

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

今朝でかける前に出題されていることを思いだした。5問とももう40人以上正答者がいた。ウォーミングアップのつもりなのだろうか。慌ててこのProblem 345だけざっと見た。ふつうに考えるとO((N+1)!)くらいはかかりそうだ。電車の中で小さいところから考えたら、すぐに漸化式を思いついた。そこでノートを取り出して計算量を計算してみると、O(N³logN)くらいだろうか。出勤してPythonでさっさと組んで、始業時間までに答えを出した。
0.4sくらいかかった。DPならもう少し速いだろうか。