1. A – Shift （WA 5）
k個はスキップして、(n-k)個はそのまま出力して、k個 0を出しました。
(defun main ()
(let* ((n (read))
(k (read)))
(loop repeat k
do (read))
(loop repeat (- n k)
do (princ (read))
(princ #\space))
(loop repeat k
do (princ 0)
(princ #\space))))
#-swank(main)Code language: PHP (php)
1.1. コード
前提として k <= n を考えていましたが、 k > n のケースがあります。
そのままだと、0 を多く出し過ぎてしまいます。
なので、 k > n のときは、 n に丸めておく必要がありました。
(defun main ()
(let* ((n (read))
(k (read))
(m (min n k)))
(loop repeat m
do (read))
(loop repeat (- n k)
do (princ (read))
(princ #\space))
(loop repeat m
do (princ 0)
(princ #\space))))
#-swank(main)Code language: PHP (php)
2. B – Potions
回復薬は1つしか使わないので、 X – H となる回復薬を探せばよいです。
(defun main ()
(let* ((N (read))
(H (read))
(X (read)))
(loop repeat N
for p = (read)
for i from 1
until (>= p (- X H))
finally (princ i))))
#-swank(main)Code language: PHP (php)
3. C – Nice Grid
このグリッドパターンには見覚えがありました。
2 次元座標平面があり、座標が (x, y) である格子点は が偶数のとき黒、奇数のとき白で塗られています。
【AtCoder ABC449D】Make Target 2を考える（Common Lisp） – Chiilabo Note
(defun white-p (row col)
(let ((x (- row 8))
(y (- col 8)))
(evenp (max (abs x) (abs y)))))
(defun main()
(princ (if (white-p (read) (read))
"white" "black")))
#-swank(main)
Code language: PHP (php)
ちなみに、表示して見てみます。
(defun print-grid ()
(loop for r from 1 to 15 do
(loop for c from 1 to 15 do
(princ (if (white-p r c) #\. #\#)))
(terpri)))Code language: PHP (php)* (print-grid)
###############
#.............#
#.###########.#
#.#.........#.#
#.#.#######.#.#
#.#.#.....#.#.#
#.#.#.###.#.#.#
#.#.#.#.#.#.#.#
#.#.#.###.#.#.#
#.#.#.....#.#.#
#.#.#######.#.#
#.#.........#.#
#.###########.#
#.............#
###############Code language: Lisp (lisp)4. D – Dentist Aoki
それぞれの場所へのアクセス回数を記録して、偶数か奇数かをチェックすればよいです。
(defun count-remain (N lst)
(let ((vec (make-array N :initial-element 0)))
(loop for a in lst
do (incf (aref vec (1- a))))
(loop for b across vec
count (evenp b))))
(defun main ()
(let* ((N (read))
(Q (read))
(Tn (loop repeat Q collect (read))))
(princ (count-remain N Tn))))
#-swank(main)Code language: PHP (php)
時間内に解けたのは、この問題まででした。
5. E – Candy Tribulation (MLE 35)
すべての子どもの飴の重さがN個の等号でつながるので、N-1個の連立方程式の解として、N個の重い飴の個数を求めます。
重い飴の個数は、「An以下の整数」であり、また最大になるように取る必要があるので、定まるか、見つからないか、の答えが出る構造です。
まずは、一番飴の個数が少ないケースで、可能な重さのリストを大きな順に並べました。
;; (weights 6 8 '(11 10 13))
;;=> (80 78 76 74 72 70 68 66 64 62 60)
(defun weights (x y An)
(let ((min (reduce #'min An)))
(loop for n from min downto 0
collect (+ (* y n)
(* x (- min n))))))Code language: Lisp (lisp)その重さがそれぞれの個数で割り切れるか、また飴の個数が負にならないか調べました。
(defun can-tribute-candy-p (x y a weight)
(multiple-value-bind (n reminder)
(floor (- weight (* x a))
(- y x))
(and (zerop reminder)
(>= n 0) )))Code language: Lisp (lisp)全員で、その重さでうまく配れたら、最後にそれぞれの人に配った重い飴の個数を合計しました。
(defun all-heavy-candys (x y An weight)
(loop for a in An
sum (floor (- weight (* x a))
(- y x))))
(defun solve (x y An)
(loop for w in (weights x y An)
when (loop for a in An
always (can-tribute-candy-p x y a w))
do (return (all-heavy-candys x y An w))
finally (return -1)))
(defun main ()
(let* ((N (read))
(x (read))
(y (read))
(An (loop repeat N collect (read))))
(princ (solve x y An))))
#-swank(main)Code language: PHP (php)
5.1. リストを作らずにループ（AC）
あらかじめ重さの候補をリストにしていたのが、メモリ制限超過になっていたので、計算しながら数をカウントしました。
A個のうち n 個を重い方のキャンディを配ったときの１人分の総重量 candy-weight は、n y + (a – n) x です。
(defun candy-weight (x y a n)
(+ (* y n)
(* x (- a n))))Code language: Lisp (lisp)あと、1人分の総重量には最小値があり、もっとも個数の多い人がすべて軽い方のキャンディだった場合です。
これを、ループの終端にしました。
(defun solve/2 (x y An)
(let* ((min (reduce #'min An))
(max (reduce #'max An))
(minimum-weight (* max x)))
(loop for n from min downto 0
for weight = (candy-weight x y min n)
while (>= weight minimum-weight)
when (loop for a in An
always (can-tribute-candy-p x y a weight))
do (return (all-heavy-candys x y An weight))
finally (return -1))))
(defun main/2 ()
(let* ((N (read))
(x (read))
(y (read))
(An (loop repeat N collect (read))))
(princ (solve/2 x y An))))
#-swank(main/2)
Code language: PHP (php)無事に全部正解になりました。
コード全体は
(defun candy-weight (x y a n)
(+ (* y n)
(* x (- a n))))
(defun can-tribute-candy-p (x y a weight)
(multiple-value-bind (n reminder)
(floor (- weight (* x a))
(- y x))
(and (zerop reminder)
(>= n 0) )))
(defun all-heavy-candys (x y An weight)
(loop for a in An
sum (floor (- weight (* x a))
(- y x))))
(defun solve/2 (x y An)
(let* ((min (reduce #'min An))
(max (reduce #'max An))
(minimum-weight (* max x)))
(loop for n from min downto 0
for weight = (candy-weight x y min n)
while (>= weight minimum-weight)
when (loop for a in An
always (can-tribute-candy-p x y a weight))
do (return (all-heavy-candys x y An weight))
finally (return -1))))
(defun main/2 ()
(let* ((N (read))
(x (read))
(y (read))
(An (loop repeat N collect (read))))
(princ (solve/2 x y An))))
#-swank(main/2)
Code language: Lisp (lisp)