1. A – Buy a Pen
入力文字列と、:blueなどのキーワードシンボルで比較したかったのですが、うまくできず。
とりあえず、文字列比較で。
;; (min-pen-price 20 30 10 "Blue") ;=> 20
(defun min-pen-price (r g b color)
(cond
((string= color "Red") (min g b))
((string= color "Blue") (min r g))
((string= color "Green") (min r b))))
(defun main ()
(princ (min-pen-price (read) (read) (read) (read-line))))
#-swank(main)Code language: Lisp (lisp)
2. B – Exact Price
基本的には X が 100 に割り切れるかで、あとは例外となる 0未満を除外しました。
(defun print-yesno (c)
(declare (type boolean c))
(princ (if c "Yes" "No")))
(defun main ()
(let ((x (read)))
(print-yesno (and (> x 0)
(= 0 (mod x 100))))))
#-swank(main)Code language: Lisp (lisp)
3. C – Grid Walk
グリッドを動く問題は、多いです。
インタープリタのようにコマンドを解釈し、有効なときだけ位置を更新しました。
行・列の座標系が、x-y座標と 90度 ずれていること、0起算と1起算に注意が必要ですね。
(defun make-grid (H W lines)
(let ((grid (make-array (list H W) :element-type 'character
:initial-element #\.)))
(loop for line in lines
for i below H
do (loop for ch across line
for j below W
do (setf (aref grid i j) ch))
finally (return grid))))
(defun next-pos (i j dir)
(case dir
(#\L (cons i (1- j)))
(#\R (cons i (1+ j)))
(#\U (cons (1- i) j))
(#\D (cons (1+ i) j))))
(defun move-commands (H W i j grid commands)
(loop for dir across commands
with ci = (1- i)
with cj = (1- j)
for next = (next-pos ci cj dir)
for ni = (car next)
for nj = (cdr next)
when (and (<= 0 ni (1- H))
(<= 0 nj (1- W))
(eql (aref grid ni nj) #\.))
do (setf ci ni
cj nj)
finally (return (cons ci cj))))
(defun main ()
(let* ((H (read))
(W (read))
(Si (read))
(Sj (read))
(grid (make-grid H W (loop repeat H collect (read-line))))
(commands (read-line))
(pos (move-commands H W Si Sj grid commands)))
(format t "~a ~a" (1+ (car pos)) (1+ (cdr pos)))))
#-swank(main)
Code language: Lisp (lisp)
この問題までで時間切れになりました。
4. D – Perfect
この問題では、イベントの後半の数値は重複しない約束なので無視でき、ただそれぞれの参加者の解答数をカウントしていけばよいことになります。
(defun perfect-participants (N M events)
(loop for (a b) in events
with memo = (make-array N :initial-element 0)
do (incf (aref memo (1- a)))
when (= M (aref memo (1- a)))
collect a))
;; (perfect-participants 3 2 '((1 1) (3 2) (2 1) (3 1) (1 2)))
;;=> (3 1)
(defun main ()
(let* ((N (read))
(M (read))
(K (read))
(events (loop repeat K
collect (list (read) (read)))))
(loop for p in (perfect-participants N M events)
do (princ p)
(princ #\space))))
#-swank(main)Code language: Lisp (lisp)
5. E – Keys
キーの有無をビットパターンで表現し、それを総当り法で条件に適合しているものを求めました。
はじめは、simple-bit-vectorで解決しようと思いましたが、ビット全探索では数値の方が実装しやすかったです。
- 【Common Lisp】ビット演算の基本の使い方（bignumとsimple-bit-vector） – Chiilabo Note
- 【Common Lisp】ビット全探索の基本（N個から選ぶ全列挙） – Chiilabo Note
;; (check-keys/naive 3 2 ts #b101) ;=> T
;; (check-keys/naive 3 2 ts #b110) ;=> T
;; (check-keys/naive 3 2 ts #b111) ;=> NIL
(defun check-keys/naive (N K tests pattern)
(declare (ignore N))
(loop for test in tests
for keys = (car test)
for r = (cdr test)
always (cond
((eq r 'O)
(>= (count-pattern pattern keys) K))
((eq r 'X)
(< (count-pattern pattern keys) K))
(t t))))
;; (count-keys/naive 3 2 ts) ;=> 2
(defun count-keys/naive (N K tests)
(loop for pattern from 0 below (expt 2 N)
count (check-keys/naive N K tests pattern)))
;; (count-pattern #b101 #b111) ;=> 2
;; pattern is expressed by bit-mask
(defun count-pattern (pattern keys)
(count-bit-mask (logand pattern keys)))
;; (count-bit-mask #b11010) ;=> 3
(defun count-bit-mask (mask)
(loop for i below (integer-length mask)
count (logbitp i mask)))
(defun set-flag (mask i)
(logior mask (ash 1 i)))
;; ((#b111 . O) (#b110 . X))
(defun read-tests (N M)
(declare (ignore N))
(loop repeat M
for C = (read)
for keys = (loop repeat C
with mask = 0
for k = (read)
do (setf mask (set-flag mask (1- k)))
finally (return mask))
for ret = (read)
collect (cons keys ret)))
(defun main ()
(let* ((N (read))
(M (read))
(K (read))
(tests (read-tests N M)))
(princ (count-keys/naive N K tests))))
#-swank(main)Code language: Lisp (lisp)素朴な方法なので時間内に解けないと思ったのですが、 の制約のため解けました。
時間がかかりましたが、全部解けました。
