Problem 145

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

とりあえずナイーブなもの。

import Data.Char
revInt ::Integer -> Integer
revInt = read.reverse.show
reversible n = mod n 10 /=  && (all odd.map digitToInt.show.(+n).revInt) n
p145 n = filter reversible [1..n]
main = print.length.p145$10^5

もちろん解けない（計算時間的な意味で）。

悪くはないと思うけど、今回は探索範囲が10^9だから、このままではつらい。

さて、これからどうするか。

[追記]

繰り上がりを考えるとそれが伝播されていく。

rev  (,) = 1
rev  _     = 
rev 1 (,) = 
rev 1 (1,) = 
rev 1 (,1) = 5
rev 1 (1,1) = 5
rev 2 (,) = 30
rev 2 (1,) = 
rev 2 (,1) = 
rev 2 (1,1) = 25
rev d (,) = 30 * (rev (d-2) (,))
rev d (1,) = 20 * (rev (d-2) (,1))
rev d (,1) = 25 * (rev (d-2) (1,))
rev d (1,1) = 25 * (rev (d-2) (1,1))
reversible 1 = 
reversible d = 20 * (rev (d-2) (,) + rev (d-2) (,1))
main = print.sum.map reversible $ [1..9]

速くなった。探索範囲が10^100でも大丈夫。

DPでもつかえば、もっと速くなるはず。

というか、手計算で求まるはず。

コンテンツ

[追記]