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を使用します。

最後に

面白そうだったので、ノリと勢いで記事を作成してみました。
問題ごとに何かコメント書いたほうが良かったかな・・・?
まだまだ未熟者なので、間違ってたり、もっと良いやり方あるよ、とかあったら教えてくれると嬉しいです。

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.