1. A – Repdigit
一桁目の数字を記憶して、再帰で不一致があるか解きました。
;; (repdigit-p 111) ;=> T
;; (repdigit-p 100) ;=> NIL
(defun repdigit-p (n)
(labels ((rec (n d)
(cond
((= n 0) t)
((= (mod n 10) d)
(rec (floor n 10) d))
(t nil))))
(rec n (mod n 10))))
(defun print-yesno (c)
(declare (type boolean c))
(princ (if c "Yes" "No")))
(defun main ()
(print-yesno (repdigit-p (read))))
#-swank(main)Code language: Lisp (lisp)
2. B – Isosceles
論理和 or です。
;; (isosceles-p 4 2 4) ;=> T
(defun isosceles-p (a b c)
(or (= a b) (= a c) (= b c)))
(defun print-yesno (c)
(declare (type boolean c))
(princ (if c "Yes" "No")))
(defun main ()
(print-yesno (isosceles-p (read) (read) (read))))
#-swank(main)Code language: Lisp (lisp)
3. C – Election
ハッシュテーブルで、投票数をカウントしました。
;; (elected-name '("x" "y" "xx" "y" "z")) ; => "y"
(defun elected-name (names)
(let ((ht (make-hash-table :test #'equal)))
(loop for name in names
do (setf (gethash name ht 0)
(1+ (gethash name ht 0))))
(loop for name being each hash-key of ht
using (hash-value voted)
with max = 0
with result = ""
when (< max voted)
do (setf result name)
(setf max voted)
finally (return result))))
(defun main ()
(let* ((n (read))
(names (loop repeat n collect (read-line))))
(princ (elected-name names))))
#-swank(main)Code language: Lisp (lisp)
4. D – Same Name
姓名を分ける必要がないので、ハッシュテーブルでカウント数が2があるか調べました。
thereisで確認したら早期終了しています。
;; (same-names '("tanaka taro" "sato hanako" "tanaka taro")) ;=> T
(defun same-name-p (names)
(let ((ht (make-hash-table :test #'equal)))
(loop for name in names
do (setf (gethash name ht 0)
(1+ (gethash name ht 0))))
(loop for name being each hash-key of ht
using (hash-value number)
thereis (>= number 2))))
(defun print-yesno (c)
(declare (type boolean c))
(princ (if c "Yes" "No")))
(defun main ()
(let* ((n (read))
(names (loop repeat n collect n)))
(print-yesno (same-name-p names))))
#-swank(main)Code language: Lisp (lisp)
ここまでで時間切れになりました。
5. E – Spiral Rotation
まずは、素朴に実装しました。
操作のときには、gridを直接操作すると競合してしまうので、いったんtempにコピーしてから、その値を使って、更新値を求めています。
(defun make-grid (N lines)
(let ((grid (make-array (list N N)
:element-type 'character
:initial-element #\.)))
(loop for row below N
for line in lines
do (loop for ch across line
for col below N
do (setf (aref grid row col) ch))
finally (return grid))))
(defun copy-grid! (N from to)
(loop for row below N
do (loop for col below N
do (setf (aref to row col)
(aref from row col)))
finally (return to)))
(defun manipulate-one! (N grid temp i)
(copy-grid! N grid temp)
(loop for x from i to (+ N 1 (- i))
do (loop for y from i to (+ N 1 (- i))
do (setf (aref grid (1- y) (- N x))
(aref temp (1- x) (1- y)))))
grid)
(defun manipulate! (N grid)
(let ((temp (make-array (list N N)
:element-type 'character
:initial-element #\.)))
(loop for i from 1 to (floor N 2)
do (manipulate-one! N grid temp i))
grid))
(defun read-lines (N)
(loop for row below N
collect (read-line)))
(defun main ()
(let* ((n (read))
(lines (read-lines n))
(grid (make-grid n lines))
)
(print-grid n (manipulate! n grid))))
#-swank(main)Code language: Lisp (lisp)5.1. 外周からの距離を4で割る
この変換をよく観察してみると、周辺からの距離によって90度ずつ回転していることがわかります。
そして、4回回転すると、一周します。
そこで、位置 (x, y) は元のグリッドと周辺からの距離（grid-shell-index）で計算できます。
(defun make-grid (N lines)
(let ((grid (make-array (list N N)
:element-type 'character
:initial-element #\.)))
(loop for row below N
for line in lines
do (loop for ch across line
for col below N
do (setf (aref grid row col) ch))
finally (return grid))))
(defun copy-grid! (N from to)
(loop for row below N
do (loop for col below N
do (setf (aref to row col)
(aref from row col)))
finally (return to)))
;; (grid-shell-index 8 1 3) ;=> 1
;; (grid-shell-index 8 8 2) ;=> 1
;; (grid-shell-index 8 6 3) ;=> 3
(defun grid-shell-index (N x y)
(min x y (- (1+ N) x) (- (1+ N) y)))
;; (x, y) --> (y', N + 1 - x')
;; therefore (x' y') <-- (N+1-y x)
(defun rotate-transition (N grid x y)
(let ((shell (grid-shell-index N x y)))
(case (mod shell 4)
(1 (aref grid (- N y) (1- x)))
(2 (aref grid (- N x) (- N y)))
(3 (aref grid (1- y) (- N x)))
(0 (aref grid (1- x) (1- y))))))
(defun manipulate/rotate! (N grid)
(let ((temp (make-array (list N N)
:element-type 'character
:initial-element #\.)))
(copy-grid! N grid temp)
(loop for x from 1 to N do
(loop for y from 1 to N do
(setf (aref grid (1- x) (1- y))
(rotate-transition N temp x y)))
)
grid))
;; I/O
(defun read-lines (N)
(loop for row below N
collect (read-line)))
(defun print-grid (N grid)
(loop for x from 1 to N
do (loop for y from 1 to N
do (princ (aref grid (1- x) (1- y))))
(terpri)))
(defun main/rotate ()
(let* ((n (read))
(lines (read-lines n))
(grid (make-grid n lines))
)
(print-grid n (manipulate/rotate! n grid))))
#-swank(main/rotate)
Code language: Lisp (lisp)
無事に全問解答できました。
