1. A – Chompers
これは、subseqの添字と問題の数値の対応を確認すれば、OKです。
;; (chomp "chemotherapy" 3) ;=> "mother"
(defun chomp (s n)
(subseq s n (- (length s) n)))
(defun main ()
(princ (chomp (read-line) (read))))
#-swank(main)Code language: Lisp (lisp)
2. B – Count Adjacent Cells
基本的には、四隅が2, 辺が3, そのほかが4です。
でも、1列だけ、1行だけというときは、1〜2。
そして、1マスだけのときは、0 と場合分けをしました。
(defun print-adjacent-cells (h w)
(cond
((= 1 h w) (print-one-cell))
((= h 1) (print-row-cells w))
((= w 1) (print-column-cells h))
(t (loop for i from 1 to h
do (loop for j from 1 to w
for a = (if (or (= i 1) (= i h)) -1 0)
for b = (if (or (= j 1) (= j w)) -1 0)
do (princ (+ 4 a b))
(princ #\space))
(terpri)))))
(defun print-one-cell ()
(princ 0))
(defun print-row-cells (w)
(loop for j from 1 to w
for b = (if (or (= j 1) (= j w)) -1 0)
do (princ (+ 2 b))
(princ #\space)))
(defun print-column-cells (h)
(loop for i from 1 to h
for a = (if (or (= i 1) (= i h)) -1 0)
do (princ (+ 2 a))
(terpri)))
(defun main ()
(print-adjacent-cells (read) (read)))
#-swank(main)Code language: Lisp (lisp)
3. C – C Stands for Center
まずは、”ABCCA”のパターンを手動で計算してみました。
Cの位置を求めて、それと先頭・末尾との距離を図ります。
c-pos = 3,4
len = 5
pos 3 -> pat = 3 min (5-3+1) , (3)
pos 4 -> pat = 2 min (5-4+1) , (4)できたコードは、
;; (center-c-substrings "ABCCA") ;=> 5
(defun center-c-substrings (s)
(let ((c-pos (loop for ch across s
for i from 1
when (eql ch #\C)
collect i))
(len (length s)))
(loop for pos in c-pos
sum (min pos (- (1+ len) pos)))))
(defun main ()
(princ (center-c-substrings (read-line))))
#-swank(main)Code language: Lisp (lisp)
4. D – Chalkboard Median（TLE22）
まずは、素朴な解をつくりました。
(defun list-median/naive (X Qn)
(loop for (a b) in Qn
with lst = (list X)
do (push a lst)
(push b lst)
(setf lst (sort lst #'<))
(princ (nth (/ (1- (length lst)) 2) lst))
(terpri)))
(defun main ()
(let* ((x (read))
(q (read))
(Qn (loop repeat q collect (list (read) (read)))))
(list-median/naive x Qn))
)
#-swank(main)
;; (list-median/naive 5 '((2 3) (1 2) (8 9)))Code language: Lisp (lisp)これは、さすがに毎回ソートするのは大変です。
4.1. 左右に分けてみた（TLE20）
そこで、Xを中央として、それより小さいもののリスト leftと、大きいもののリスト right に分けて追加することにしました。
クエリの数値 a, b の間に x があるときには、そのまま追加するだけで、そうでないときは、片側のリストに追加してから中央にもっとも近い数値を取り出します。
; (cadr '(1 2 3)) ; 2
(defun list-median/2 (X Qn)
(loop with left = nil
with right = nil
with center = X
for q in Qn
for a = (min (car q) (cadr q))
for b = (max (car q) (cadr q))
do (cond
((< x a) (progn
(push x left)
(push a right)
(push b right)
(setf right (sort right #'<))
(setf x (pop right))))
((< b x) (progn
(push x right)
(push a left)
(push b left)
(setf left (sort left #'>))
(setf x (pop left))))
(t (progn
(push a left)
(push b right))))
(princ x)
(terpri)))
(defun main ()
(let* ((x (read))
(q (read))
(Qn (loop repeat q collect (list (read) (read)))))
(list-median/2 x Qn))
)
#-swank(main)Code language: Lisp (lisp)2問解けましたが、まだまだです。
4.2. 優先度付きキューの実装にした（444 ms）
leftは最大値を、rightは最小値を取り出しているので、優先度付きキューの実装を使うことにしました。
(defun list-median/pq (X Qn)
(loop with left = (make-pairing-pq :order #'>)
with right = (make-pairing-pq :order #'<)
with center = X
for q in Qn
for a = (min (car q) (cadr q))
for b = (max (car q) (cadr q))
do (cond
((< x a) (progn
(pq-push/pairing x left)
(pq-push/pairing a right)
(pq-push/pairing b right)
(setf x (pq-pop/pairing right))))
((< b x) (progn
(pq-push/pairing x right)
(pq-push/pairing a left)
(pq-push/pairing b left)
(setf x (pq-pop/pairing left))))
(t (progn
(pq-push/pairing a left)
(pq-push/pairing b right))))
(princ x)
(terpri)))Code language: Lisp (lisp)
コード全体は
(defstruct pairing-pq
(data nil)
(order #'<))
(defun pq-empty-p/pairing (pq)
(null (pairing-pq-data pq)))
(defun %meld (a b order)
(cond
((null a) b)
((null b) a)
((funcall order (car b) (car a))
(cons (car b) (cons a (cdr b))))
(t
(cons (car a) (cons b (cdr a))))))
(defun %pairwise-meld (heaps order)
(cond
((null heaps) nil)
((null (cdr heaps)) (car heaps))
(t
(%meld (%meld (first heaps)
(second heaps)
order)
(%pairwise-meld (cddr heaps) order)
order))))
(defun pq-push/pairing (x pq)
(setf (pairing-pq-data pq)
(%meld (cons x nil)
(pairing-pq-data pq)
(pairing-pq-order pq)))
pq)
(defun pq-pop/pairing (pq)
(let ((h (pairing-pq-data pq)))
(when h
(setf (pairing-pq-data pq)
(%pairwise-meld (cdr h)
(pairing-pq-order pq)))
(car h))))
(defun pq-peek/pairing (pq)
(car (pairing-pq-data pq)))
;;===
(defun list-median/pq (X Qn)
(loop with left = (make-pairing-pq :order #'>)
with right = (make-pairing-pq :order #'<)
with center = X
for q in Qn
for a = (min (car q) (cadr q))
for b = (max (car q) (cadr q))
do (cond
((< x a) (progn
(pq-push/pairing x left)
(pq-push/pairing a right)
(pq-push/pairing b right)
(setf x (pq-pop/pairing right))))
((< b x) (progn
(pq-push/pairing x right)
(pq-push/pairing a left)
(pq-push/pairing b left)
(setf x (pq-pop/pairing left))))
(t (progn
(pq-push/pairing a left)
(pq-push/pairing b right))))
(princ x)
(terpri)))
(defun main ()
(let* ((x (read))
(q (read))
(Qn (loop repeat q collect (list (read) (read)))))
(list-median/pq x Qn)))
#-swank(main)
Code language: Lisp (lisp)