1. A – First Contest of t Year(WA 2)
;; (next-year-contest-day 7 365 4) ; => 3
;; (next-year-contest-day 7 10 5) ; => 2
;; F mod W ≡ N + D mod W
(defun next-year-contest-day (w d f)
(mod (- f d) w))
(defun main ()
(let ((w 7)
(d (read))
(f (read)))
(princ (next-year-contest-day w d f))))
#-swank(main)
Code language: Lisp (lisp)
1.1. 割り切れる場合は7になる
;; (next-year-contest-day 7 365 4) ; => 3
;; (next-year-contest-day 7 10 5) ; => 2
;; (next-year-contest-day 7 10 3) ; => 7 (/= 0)
;; F mod W ≡ N + D mod W
(defun next-year-contest-day (w d f)
(let ((n (mod (- f d) w)))
(cond
((zerop n) w)
(t n))))
(defun main ()
(let ((w 7)
(d (read))
(f (read)))
(princ (next-year-contest-day w d f))))
#-swank(main)
Code language: Lisp (lisp)
2. B – Intersection
;; (length-painted-both 0 3 1 5) ;=> 2
;; (length-painted-both 0 1 4 5) ;=> 0
;; (length-painted-both 0 3 3 7) ;=> 0
(defun length-painted-both (L1 R1 L2 R2)
(cond
((<= R1 L2) 0)
((<= R2 L1) 0)
(t (- (min R1 R2) (max L1 L2)))))
(defun main ()
(princ (length-painted-both
(read) (read) (read) (read))))
#-swank(main)Code language: Lisp (lisp)
3. C – Strawberries
;; (consecutive-healthy-tooth "OOXOOOO") ;=> (2 4)
(defun consecutive-healthy-tooth (str)
(loop for ch across str
with lst = '()
with cnt = 0
when (eql ch #\O)
do (incf cnt)
when (and (eql ch #\X)
(> cnt 0))
do (push cnt lst)
(setf cnt 0)
finally (when (> cnt 0)
(push cnt lst))
(return (nreverse lst))))
;; (max-strawberries-eaten 3 "OOXOOOO") ; => 1
;; (max-strawberries-eaten 2 "OXXOOOXOOOOX") ; => 3
;; (max-strawberries-eaten 5 "XXOOOOOOOOXXOOOOOXXXXX") ; => 2
(defun max-strawberries-eaten (k str)
(let ((lst (consecutive-healthy-tooth str)))
(loop for n in lst
sum (floor n k))))
(defun main ()
(let ((N (read))
(K (read))
(S (read-line)))
(declare (ignore N))
(princ (max-strawberries-eaten K S))))
#-swank(main)Code language: Lisp (lisp)
4. D – TaK Code
グリッドの最大サイズが100×100なので、素直に条件を判定しました。
(defun make-grid (N M lines)
(let ((grid (make-array (list N M)
:element-type 'bit
:initial-element 0)))
(loop for str in lines
for row below N
do (loop for ch across str
for col below M
do (setf (aref grid row col)
(if (eql ch #\#) 1 0)))
finally (return grid))))
;; (valid-tak-code-at-p 19 18 *grid* 0 0) ;=> T
;; (valid-tak-code-at-p 19 18 *grid* 1 1) ;=> NIL
(defun valid-tak-code-at-p (N M grid row col)
(cond ((and (<= 0 row (- N 9))
(<= 0 col (- M 9)))
(and
(= 0 (aref grid (+ row 3) (+ col 3)))
(= 0 (aref grid (+ row 5) (+ col 5)))
(loop for i from 0 to 2
always (= 0 (aref grid (+ row i)
(+ col 3)))
always (= 0 (aref grid (+ row i 6)
(+ col 5)))
always (= 0 (aref grid (+ row 3)
(+ col i)))
always (= 0 (aref grid (+ row 5)
(+ col i 6)))
always (loop for j from 0 to 2
always (= 1 (aref grid
(+ row i)
(+ col j)))
always (= 1 (aref grid
(+ row i 6)
(+ col j 6)))))))
(t nil)))
;; (satisfies-ij-list 19 18 *grid*)
;; => ((0 0) (0 9) (6 6) (9 1))
(defun satisfies-ij-list (N M grid)
(loop for i below N
append (loop for j below M
when (valid-tak-code-at-p N M grid i j)
collect (list i j))))
(defun read-lines (M)
(loop repeat M collect (read-line)))
(defun main ()
(let* ((N (read))
(M (read))
(Sn (read-lines N))
(grid (make-grid N M Sn)))
(loop for (i j) in (satisfies-ij-list N M grid)
do (format t "~a ~a~%" (1+ i) (1+ j)))))
#-swank(main)
Code language: Lisp (lisp)
5. E – 1111gal password（197ms）
最初は、シンプルな再帰で解きました。
(defparameter *prime* 998244353)
;; (satisfied-patterns/rec 4) ;=> 203
(defun satisfied-patterns/rec (N)
(labels ((rec (N d)
(mod (cond
((= N 0) 0)
((= N 1) 1)
((= d 1) (+ (rec (1- N) 1)
(rec (1- N) 2)))
((= d 9) (+ (rec (1- N) 8)
(rec (1- N) 9)))
(t (+ (rec (1- N) (1- d))
(rec (1- N) d)
(rec (1- N) (1+ d)))))
*prime*)))
(loop for digit from 1 to 9
sum (rec N digit))))Code language: JavaScript (javascript)しかし、再計算が多く時間がかかりますし、Nが1,000,000だと、スタックオーバーフローになってしまいました。
次に、ハッシュテーブルでdp[N, d] を記録する方法を取っていましたが、これも N = 1,000,000 だとTLEでした。
そこで、動的計画法で prev と now の２つの配列を順次更新していくようにして、解くことができました。
(defparameter *prime* 998244353)
(defun satisfied-highest (N d prev now)
(setf (aref now d)
(mod
(cond
((= N 0) 0)
((= N 1) 1)
((= d 1) (+ (aref prev 1)
(aref prev 2)))
((= d 9) (+ (aref prev 8)
(aref prev 9)))
( t (+ (aref prev (1- d))
(aref prev d)
(aref prev (1+ d)))))
*prime*)))
;; (satisfied-patterns 4) ; => 203
;; (satisfied-patterns 1000000) ;=> 248860093
(defun satisfied-patterns (N)
(let ((now (make-array 10 :element-type 'fixnum
:initial-element 0))
(prev (make-array 10 :element-type 'fixnum
:initial-element 0)))
(loop for i from 1 to (1- N)
do (loop for d from 1 to 9
do (satisfied-highest i d prev now))
do (loop for d from 1 to 9
do (setf (aref prev d) (aref now d))))
(mod
(loop for d from 1 to 9
sum (satisfied-highest N d prev now))
*prime*)))
(defun main ()
(let ((N (read)))
(princ (satisfied-patterns N))))
#-swank(main)Code language: Lisp (lisp)
5.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 まで短縮できました。
ただ、
