始めに
数日前に唐突にLISPに入門したのでやってみました。 qiita.com
参考資料
AtCoderをCommon Lispで解いた人の記事
- AtCoder に登録したら解くべき精選過去問 10 問を Common Lisp で解いてみた - Qiita
- competitive: 競技プログラミングでCommon Lispを使っている人とこれから使うかもしれない人のために
- CommonLispでAtCoderを100問くらい解いたので纏める - takeokunn's blog
第1問 ABC 086 A - Product
(defun solve (a b) (if (= (mod (* a b) 2) 0) "Even" "Odd") ) (format t "~A~%" (solve (read) (read)))
入力は(read), (read-char), (read-line)を使う。それぞれ整数、文字、文字列を読み込む。出力にはprincやformatがある。
関数の定義にはdefunを使う。関数は前置記法つまり(関数名 引数1 引数2 ...)で書く。
余りにはmod, 'rem'がある。違いは負の数の扱い。
第2問 ABC 081 A - Placing Marbles
(defun solve (a b c) (+ (if (equal a #\1) 1 0) (if (equal b #\1) 1 0) (if (equal c #\1) 1 0)) ) (princ (solve (read-char) (read-char) (read-char)))
文字や文字列の比較にはchar=, string=, equalがある。
第3問 ABC 081 B - Shift Only
(defun two_count (a) (if (= (mod a 2) 1) 0 (+ (two_count (/ a 2)) 1)) ) (defun solve (n) (if (> n 0) (min (two_count (read)) (solve (- n 1))) 30) ) (princ (solve (read)))
LISPは動的型付けなので/だと有理数になることに注意。切り捨てにはfloor, truncateを使用する。違いは負の数の扱い。
第4問 ABC 087 B - Coins
(defun solve (a b c x) (if (> a 0) (+ (solve (- a 1) b c x) (solve 0 b c (- x (* 500 a)))) (if (> b 0) (+ (solve a (- b 1) c x) (solve a 0 c (- x (* 100 b)))) (if (> c 0) (+ (solve a b (- c 1) x) (solve a b 0 (- x (* 50 c)))) (if (= x 0) 1 0) ) ) ) ) (princ (solve (read) (read) (read) (read)))
第5問 ABC 083 B - Some Sums
(defun digit_sum (n) (if (> n 0) (+ (digit_sum (floor n 10)) (mod n 10)) 0) ) (defun solve (n a b) (let ((x (digit_sum n))) (if (> n 0) (+ (solve (- n 1) a b) (if (and (<= a x) (<= x b)) n 0)) 0) ) ) (princ (solve (read) (read) (read)))
変数にはletを使う。
第6問 ABC 088 B - Card Game for Two
(defun solve (n a) (if (equal a nil) 0 (if (= n 0) (+ (solve 1 (cdr a)) (car a)) (- (solve 0 (cdr a)) (car a)) ) ) ) (defun init (n) (if (> n 0) (append (init (- n 1)) (list (read))) (list)) ) (let ((a (init (read)) )) (princ (solve 0 (sort a #'>))) )
listでリストを作ることができる。carで先頭の要素を取得し、cdrで以降の要素を取得する。sortで比較関数を指定してソートする。
ちなみにlengthで長さが取得できるが、線形時間なので注意。空リストかどうかを判定したいときは(equal l nil)か(null l)を使う。
第7問 ABC 085 B - Kagami Mochi
(defun solve (s a) (if (equal a nil) 1 (+ (solve (car a) (cdr a)) (if (< s (car a)) 1 0)) ) ) (defun init (n) (if (> n 0) (append (init (- n 1)) (list (read))) (list)) ) (let ((a (sort (init (read)) #'<))) (princ (solve (car a) (cdr a))) )
append, consでリストを結合する。
https://www.nak.ics.keio.ac.jp/class/lisp/union.pdf
第8問 ABC 085 C - Otoshidama
(defun select (l1 l2) (if (> (car l1) (car l2)) l1 l2) ) (let ((n (read)) (y (read))) (defun solve1 (a b) (let ((c (- n (+ a b)))) (if (and (>= c 0) (= (+ (* 10000 a) (+ (* 5000 b) (* 1000 c))) y)) (list a b c) (if (> a 0) (select (solve1 (- a 1) b) (solve2 a b)) (solve2 a b)) ) ) ) (defun solve2 (a b) (let ((c (- n (+ a b)))) (if (and (>= c 0) (= (+ (* 10000 a) (+ (* 5000 b) (* 1000 c))) y)) (list a b c) (if (> b 0) (solve2 a (- b 1)) (list -1 -1 -1)) ) ) ) (format t "~{~A~^ ~}" (solve1 n n)) )
第9問 ABC 049 C - Daydream
(defun solve (s) (let ((n (length s))) (cond ((and (>= n 5) (equal (subseq s (- n 5) n) "dream")) (solve (subseq s 0 (- n 5)))) ((and (>= n 7) (equal (subseq s (- n 7) n) "dreamer")) (solve (subseq s 0 (- n 7)))) ((and (>= n 5) (equal (subseq s (- n 5) n) "erase")) (solve (subseq s 0 (- n 5)))) ((and (>= n 6) (equal (subseq s (- n 6) n) "eraser")) (solve (subseq s 0 (- n 6)))) ((= n 0) "YES") (t "NO") ) ) ) (princ (solve (read-line)))
第10問 ABC 086 C - Traveling
(defun calc (b) (let ((ti (car b)) (x (car (cdr b))) (y (car (cdr (cdr b))))) (if (and (= (mod ti 2) (mod (+ (abs x) (abs y)) 2)) (>= ti (+ (abs x) (abs y))) ) 0 1) ) ) (defun solve (a) (if (= (loop for l in a sum (calc l)) 0) "Yes" "No") ) (defun init (n) (loop for i below n collect (list (read) (read) (read))) ) (defun delta (a) (loop for b on a collect (if (null (cdr b)) (car b) (diff (car b) (car (cdr b))) ) ) ) (defun diff (s1 s2) (list (- (car s1) (car s2)) (- (car (cdr s1)) (car (cdr s2))) (- (car (cdr (cdr s1))) (car (cdr (cdr s2)))) ) ) (princ (solve (delta (reverse (init (read))))))
105オーダーで再帰するとスタックオーバーフローするのでループを用いる。ループにはloopを使う。返り値にはcollectやsumなどがある。
【Common Lisp】loopマクロの使い方まとめ - プログラミング原人の進化論
最後に
間違いなどありましたら指摘していただけるとありがたいです。
