PE34

どうもお久しぶりです。
1年半近く(!)かかって、ようやくProblem 34を解けたので記念真紀子

できるだけ連続した番号の問題を解いていこうと考えていたが、 どうにも解法がわからんので、諦めてProblem 38に挑戦。

PE38 - BPM Memo

こんな事も書いてましたが、他の問題も難しく、、Project Euler自体放置してた。

言い訳はここらへんにして、本題。

1週間位前、電車に乗っているときに、ふと何かが降りてきたような気がして
iPhoneのちっちゃいソフトキーボードで書いてみたものの、駅につくまでに間に合わず、PCで再挑戦した。

単純に回して探索するのは論外として、
センスが無いので、探索する数の範囲をどう決めるかで長らく悩んで嵌っていた。

上で書いた、電車に乗っているときに降ってきたこととして、
数の桁数を決めて調べる方針として、
「その桁数を超えない範囲」で、「各桁の数の階乗がその桁数を超えない数」を調べれば良さそうだ、ということだった。
これでかなり小さな探索範囲になるので、早速実装してみたところ、なんとうまく行かない。。。

じっくり考えてわかったことだが、
上位桁に0のような階乗が小さい数がほとんど含まれるようなケースを考えると、
下位桁では「各桁の数の階乗がその桁数を超える数」も含めないといけない場合がありそうだった。

「指定桁数を超えない範囲」という点だけを制約として、再度書き直してみて、ようやく正解できた。