やっと解けた

Lisp

どもです。

Project Euler Problem 113 に入ってから数日。
先ほどやっとこさできました。
いい方法が思いつかなかったというか，手を動かすのが面倒で保留していたというのが
いつものいいわけ。
でも，チョコ飴をなめていたら気分がよくなったので，手をつけました。


手動で計算できんかね? とやろうとしたが，速攻挫折。Σがいっぱいできちゃった。
なのでなんか法則というか，そんなんがあるはずだから探して，
というか無理矢理つくって計算してもらった。
桁数ごとに計算していくんだけど，前回の桁数の該当数字の先頭にどの数字をつけられるか?
を考えて計算しました。

(defun euler-problem-113 ()
  (- (+ (count-increasing-numbers 100) (count-decreasing-numbers 100))
     (* 9 100)))

;; 3桁の increasing-number
(loop for k from 10 downto 2
      for n = 45 then (- n k)
      collect n)
;; => (45 36 28 21 15 10 6 3 1)

;; 4桁の increasing number
(loop for k from 10 downto 2
      for n = 165 then (- n d)
      for d = 45 then (- d k)
      summing n)
;; => 495

;; (next-increasing-list '(165 120 84 56 35 20 10 4 1))
;; => (495 330 210 126 70 35 15 5 1)
;; (reduce #'+ '(495 330 210 126 70 35 15 5 1))
;; => 1278  <-- 5桁の increasing-number の個数

(defun next-increasing-numbers-list (lst)
  (let* ((n (reduce #'+ lst)))
    (cons n
          (loop for e in (butlast lst)
                for m = (- n (car lst)) then (- m e)
                collect m))))

(defun count-increasing-numbers (num-of-digits)
  (loop for lst = '(9 8 7 6 5 4 3 2 1) then (next-increasing-list lst)
        with cnt = 0
        repeat num-of-digits
        do (incf cnt (car lst))
        finally (return cnt)))

;; decreasing number の個数を数える
(defun next-decreasing-numbers-list (lst)
  (loop for l on (mapcar #'1+ lst)
        collect (reduce #'+ l)))

(defun count-decreasing-numbers (num-of-digits)
  (loop for lst = '(9 8 7 6 5 4 3 2 1) then (next-decreasing-numbers-list lst)
        with cnt = 0
        repeat num-of-digits
        do (incf cnt (car lst))
        finally (return cnt)))


途中にメモが残っていますが，無視。
もっと時間がかかると思ったけど，はやくてびっくらこいた。
ま，それぞれ100回ずつループしているだけだからはやいのか。
最初，重複カウントした分を引く数を間違えたというのはなんたらかんたら。

CL-USER> (time (euler-problem-113))
(EULER-PROBLEM-113) took 0 milliseconds (0.000 seconds) to run 
                    with 4 available CPU cores.
During that period, 0 milliseconds (0.000 seconds) were spent in user mode
                    0 milliseconds (0.000 seconds) were spent in system mode
 65,928 bytes of memory allocated.


んで，フォーラム入ったら一発目に二項係数があってばびった。
そんな簡単に求まるのか? すげー。
ちゅうわけで，フォーラム行ってきます。