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でもつかえば、もっと速くなるはず。
というか、手計算で求まるはず。
作成者 Toru Mano
最終更新時刻 2023-01-01 (c70d5a1)