PE34
どうもお久しぶりです。
1年半近く(!)かかって、ようやくProblem 34を解けたので記念真紀子。
できるだけ連続した番号の問題を解いていこうと考えていたが、 どうにも解法がわからんので、諦めてProblem 38に挑戦。
PE38 - BPM Memo
こんな事も書いてましたが、他の問題も難しく、、Project Euler自体放置してた。
言い訳はここらへんにして、本題。
1週間位前、電車に乗っているときに、ふと何かが降りてきたような気がして
iPhoneのちっちゃいソフトキーボードで書いてみたものの、駅につくまでに間に合わず、PCで再挑戦した。
単純に回して探索するのは論外として、
センスが無いので、探索する数の範囲をどう決めるかで長らく悩んで嵌っていた。
上で書いた、電車に乗っているときに降ってきたこととして、
数の桁数を決めて調べる方針として、
「その桁数を超えない範囲」で、「各桁の数の階乗がその桁数を超えない数」を調べれば良さそうだ、ということだった。
これでかなり小さな探索範囲になるので、早速実装してみたところ、なんとうまく行かない。。。
じっくり考えてわかったことだが、
上位桁に0のような階乗が小さい数がほとんど含まれるようなケースを考えると、
下位桁では「各桁の数の階乗がその桁数を超える数」も含めないといけない場合がありそうだった。
「指定桁数を超えない範囲」という点だけを制約として、再度書き直してみて、ようやく正解できた。