Edited at

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


はじめに

もはや何番煎じかわかりませんが、自分も以下のdrkenさんの記事で紹介されている10問の問題をCommon Lispでチャレンジしてみました。

AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~


標準入出力について

標準入力にはreadread-lineを使用します。

標準出力にはformatを使用します。

以下のWebサイトにわかりやすく記載されています。


第1問: ABC 086 A - Product (100 点)

ABC 086 A - Product

(defun product (a b)

(if (zerop (rem (* a b) 2))
"Even"
"Odd"))

(format t "~A~%" (product (read) (read)))

提出例

関数定義にはdefunを使用します。

条件分岐にはifを使用します。

除算の余りを求める関数にはremmodがあります。

今回は、計算速度の速いremの方を使用しました。

[mod計算速度]

(time (dotimes (x 100000000)  (mod x 18)))

Evaluation took:

0.047 seconds of real time
0.047535 seconds of total run time (0.047535 user, 0.000000 system)
102.13% CPU
85,553,666 processor cycles
0 bytes consed

[rem計算速度]

(time (dotimes (x 100000000)  (rem x 18)))

Evaluation took:

0.036 seconds of real time
0.036126 seconds of total run time (0.036126 user, 0.000000 system)
100.00% CPU
65,030,078 processor cycles
0 bytes consed

zeropはゼロかどうか判定する関数です。


第2問: ABC 081 A - Placing Marbles (100 点)

ABC 081 A - Placing Marbles

(defun placing-marbles (s)

(let ((counter 0))
(loop :for c :across s
:do (if (string= c "1") (incf counter)))
counter))

(format t "~A~%" (placing-marbles (read-line)))

提出例

@nfunatoさんにツイッターで教えてもらった方法でやってみました。

loopのcountキーワードを使った方法です。

ただ、一つ目のケースだけ異常に遅いのが謎・・・。

(defun placing-marbles (s)

(loop :for c :across s
:count (char= c #\1)))

(format t "~A~%" (placing-marbles (read-line)))

提出例

レキシカル変数定義にはletを使用します。

loopマクロで文字列を1文字ずつ処理します。

文字&文字列の比較はchar=string=などを使用します。

インクリメント&デクリメントにはincfdecfを使用します。


第3問: ABC 081 B - Shift Only (200 点)

ABC 081 B - Shift Only

(defun shift-only (n a)

(let ((res 0)
(exist-odd nil))
(loop
(dotimes (i n)
(if (not (zerop (rem (aref a i) 2)))
(setf exist-odd t)))
(if (eq exist-odd t) (return))
(dotimes (i n)
(setf (aref a i) (/ (aref a i) 2)))
(incf res))
res))

(defun create-data ()
(let* ((n (read))
(a (make-array `(,n))))
(dotimes (i n)
(setf (aref a i) (read)))
(values n a)))

(multiple-value-bind (n a) (create-data)
(format t "~A~%" (shift-only n a)))

提出例

変数に値をセットするにはsetfを使用します。

指定した回数だけ処理を繰り返すにはdotimesを使用します。

配列の作成にはmake-array、それぞれの要素への参照はarefを使用します。

同値比較述語はeqなどを使用します。

否定はnotを使用します。

ループを途中で抜けるにはreturnを使用します。

(C言語で言うところのbreakに当たるものです。)

関数が多値を返すにはvalues、多値を受け取るにはmultiple-value-bindを使用します。


第4問: ABC 087 B - Coins (200 点)

ABC 087 B - Coins

(defun coins (a b c x)

(let ((res 0)
(total 0))
(dotimes (i (+ a 1))
(dotimes (j (+ b 1))
(dotimes (k (+ c 1))
(setf total (+ (* 500 i) (* 100 j) (* 50 k)))
(if (= total x) (incf res)))))
res))

(format t "~A~%" (coins (read) (read) (read) (read)))

提出例


第5問: ABC 083 B - Some Sums (200 点)

ABC 083 B - Some Sums

(defmacro while (test &body body)

`(do ()
((not ,test))
,@body))

(defun find-sum-of-digits (n)
(let ((sum 0))
(while (> n 0)
(setf sum (+ sum (rem n 10)))
(setf n (floor n 10)))
sum))

(defun some-sums (n a b)
(let ((total 0)
(sum 0))
(dotimes (i (+ n 1))
(setf sum (find-sum-of-digits i))
(if (and (>= sum a) (<= sum b))
(setf total (+ total i))))
total))

(format t "~A~%" (some-sums (read) (read) (read)))

提出例

マクロを作るにはdefmacroを使用します。


第6問: ABC 088 B - Card Game for Two (200 点)

ABC 088 B - Card Game for Two

(defun card-game-for-two (n a)

(let ((alice 0)
(bob 0))
(setf a (sort a #'>))
(dotimes (i n)
(if (zerop (rem i 2))
(setf alice (+ alice (aref a i)))
(setf bob (+ bob (aref a i)))))
(- alice bob)))

(defun create-data ()
(let* ((n (read))
(a (make-array `(,n))))
(dotimes (i n)
(setf (aref a i) (read)))
(values n a)))

(multiple-value-bind (n a) (create-data)
(format t "~A~%" (card-game-for-two n a)))

提出例

データを昇順または降順に整列させるにsortを使用します。


第7問: ABC 085 B - Kagami Mochi (200 点)

ABC 085 B - Kagami Mochi

(defun kagami-mochi (n a)

(let ((res 0)
(num (make-array '(110) :initial-element 0)))
(dotimes (i n)
(incf (aref num (aref a i))))
(dotimes (i 101)
(if (> (aref num i) 0)
(incf res)))
res))

(defun create-data ()
(let* ((n (read))
(a (make-array `(,n))))
(dotimes (i n)
(setf (aref a i) (read)))
(values n a)))

(multiple-value-bind (n a) (create-data)
(format t "~A~%" (kagami-mochi n a)))

提出例


第8問: ABC 085 C - Otoshidama (300 点)

ABC 085 C - Otoshidama

(defun otoshidama (n y)

(let ((res10000 -1)
(res5000 -1)
(res1000 -1)
(c 0)
(total 0))
(dotimes (a (1+ n))
(dotimes (b (- (1+ n) a))
(setf c (- n a b))
(setf total (+ (* 10000 a) (* 5000 b) (* 1000 c)))
(when (= total y)
(setf res10000 a)
(setf res5000 b)
(setf res1000 c))))
(values res10000 res5000 res1000)))

(multiple-value-bind (res10000 res5000 res1000) (otoshidama (read) (read))
(format t "~A ~A ~A~%" res10000 res5000 res1000))

提出例

whenifと似ていますが、prognを使わなくてもthen部を複数持つことが出来ます。

(else部を複数持つことができるのはunless)


第9問: ABC 049 C - Daydream (300 点)

ABC 049 C - Daydream

(defparameter +divide+

(make-array '(4)
:initial-contents
'("dream" "dreamer" "erase" "eraser")))

(defmacro while (test &body body)
`(do ()
((not ,test))
,@body))

(defun daydream (s)
(let ((can1 t)
can2
(l (length s))
(j 0)
buff
d)

(setf s (reverse s))
(dotimes (i 4)
(setf (aref +divide+ i) (reverse (aref +divide+ i))))

(while (< j l)
(setf can2 nil)
(dotimes (k 4)
(setf d (aref +divide+ k))
(if (>= l (+ (length d) j))
(setf buff (subseq s j (+ (length d) j)))
(setf buff (subseq s j)))
(when (string= buff d)
(setf can2 t)
(setf j (+ j (length d)))
(return)))
(when (not (eq can2 t))
(setf can1 nil)
(return)))

(if (eq can1 t)
"YES"
"NO")))

(format t "~A~%" (daydream (read-line)))

提出例

長さを調べるにはlengthを使用します。

データを逆順にするにはreverseを使用します。

部分列を取り出すにはsubseqを使用します。


第10問: ABC 086 C - Traveling (300 点)

ABC 086 C - Traveling

(defun traveling (n tm x y)

(let ((can t)
(dt 0)
(dist 0))
(dotimes (i n)
(setf dt (- (aref tm (+ i 1)) (aref tm i)))
(setf dist (+ (abs (- (aref x (+ i 1)) (aref x i)))
(abs (- (aref y (+ i 1)) (aref y i)))))
(if (< dt dist)
(setf can nil))
(if (not (= (rem dist 2) (rem dt 2)))
(setf can nil)))
(if (eq can t)
"Yes"
"No")))

(defun create-data ()
(let ((n (read))
(tm (make-array '(110000) :initial-element 0))
(x (make-array '(110000) :initial-element 0))
(y (make-array '(110000) :initial-element 0)))
(dotimes (i n)
(setf (aref tm (1+ i)) (read))
(setf (aref x (1+ i)) (read))
(setf (aref y (1+ i)) (read)))
(values n tm x y)))

(multiple-value-bind (n tm x y) (create-data)
(format t "~A~%" (traveling n tm x y)))

提出例

絶対値を取得するにはabsを使用します。


最後に

面白そうだったので、ノリと勢いで記事を作成してみました。

問題ごとに何かコメント書いたほうが良かったかな・・・?

まだまだ未熟者なので、間違ってたり、もっと良いやり方あるよ、とかあったら教えてくれると嬉しいです。