始めに

数日前に唐突にLISPに入門したのでやってみました。 qiita.com

参考資料

AtCoderをCommon Lispで解いた人の記事

第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

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

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

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

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

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

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

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

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

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))))))

10⁵オーダーで再帰するとスタックオーバーフローするのでループを用いる。ループにはloopを使う。返り値にはcollectやsumなどがある。
【Common Lisp】loopマクロの使い方まとめ - プログラミング原人の進化論

最後に

間違いなどありましたら指摘していただけるとありがたいです。

season's quarterly

数学/物理/プログラミング

AtCoder に登録したら解くべき精選過去問 10 問を Common Lisp で解いてみた

始めに