久々のプログラミングネタw!
暇だったので解いてみました。
まずは、愚直なコードで傾向と対策を考えますw
#
(define (iter n c)
(if (> n limit)
c
(iter (+ n 1)
(+ c (length (filter (lambda (x) (= x 55)) (map x->integer (string->list (number->string n)))))))))
(iter 1 0))
これは遅いwww
改良しました。
ポイントは計算で求めて計算量を O(N) にする事です。
(define nil '())
(define (number->list num)
(define (iter n lst)
(if (= n 0)
lst
(iter (quotient n 10) (cons (remainder n 10) lst))))
(iter num nil))
(define (count-seven n)
(let ((zk (- (length (number->list n)) 1)))
(if (< zk 1)
0
(* (quotient n (expt 10 zk)) zk (expt 10 (- zk 1))))))
(define (seven num)
(define (iter n q r s k cnt)
(if (= n 0)
cnt
(cond ((= r 7)
(iter (quotient n 10)
(quotient q 10)
(remainder q 10)
(+ s (* r (expt 10 k)))
(+ k 1)
(+ cnt (count-seven (* r (expt 10 k))) 1 s)))
((< r 7)
(iter (quotient n 10)
(quotient q 10)
(remainder q 10)
(+ s (* r (expt 10 k)))
(+ k 1)
(+ cnt (count-seven (* r (expt 10 k))))))
(else
(iter (quotient n 10)
(quotient q 10)
(remainder q 10)
(+ s (* r (expt 10 k)))
(+ k 1)
(+ cnt (count-seven (* r (expt 10 k))) (expt 10 k)))))))
(iter num (quotient num 10) (remainder num 10) 0 0 0))
ロジックの解説は暇な時にでも書きます。たぶん。
実行結果
gosh> (time (map seven '(99 77777 23678947 732465890 1912478368)))
(20 38890 16140633 614891670 1728439836)
1秒かかってないので合格です。
計算量は O(N) ですから、
gosh> (time (seven 1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890))
97379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972698737997269873799726987379972768
巨大な数でも楽々計算できます。
この答えで合ってるのか不明ですが。たぶん合ってるのだと思いますw