1.1. フリップする
少し効率化を考えました。
prev[0] = prev[10] = 0 に固定すれば、分岐はなくなります。
初期値は、prev[1]〜prev[9] = 1 にセットしておきます。
また、even-now, odd-now を持つことにして、奇数・偶数でフリップして、セットするようにしました。
(defparameter *prime* 998244353)
(defun satisfied-highest/effi (N d odd-now even-now)
(let* ((now (if (evenp N) even-now odd-now))
(prev (if (evenp N) odd-now even-now)))
(setf (aref now d)
(mod (+ (aref prev (1- d))
(aref prev d)
(aref prev (1+ d)))
*prime*))))
;; (satisfied-patterns 4) ; => 203
;; (satisfied-patterns 1000000) ;=> 248860093
(defun satisfied-patterns/effi (N)
(let ((even-now (make-array 11 :element-type 'fixnum
:initial-element 0))
(odd-now (make-array 11 :element-type 'fixnum
:initial-element 0)))
(loop for d from 1 to 9
do (setf (aref odd-now d) 1))
(loop for i from 2 to (1- N)
do (loop for d from 1 to 9
do (satisfied-highest/effi
i d odd-now even-now)))
(mod
(loop for d from 1 to 9
sum (satisfied-highest/effi N d odd-now even-now))
*prime*)))
(defun main/effi ()
(let ((N (read)))
(princ (satisfied-patterns/effi N))))
#-swank(main/effi)Code language: PHP (php)解答時間は、161 ms まで短縮できました。
ただ、
