- AtCoder ABC042のA・B・C問題をCommon Lispで解いてみました。
- Aでは3つの数を並び替えてリテラルと比較することで、五七五かどうかを判定しています。
- B問題では
string<で辞書順ソートし、formatのループディレクティブで連結して出力しています。 - C問題ではN以上の整数を順にスキャンしながら、各桁に禁止数字が含まれないかを再帰で確認しています。
1. ABC042A – 和風いろはちゃんイージー
3つの整数A、B、Cが与えられます。
A – 和風いろはちゃんイージー
{A,B,C}を並び替えた列が (5,5,7) に一致するとき「YES」、そうでなければ「NO」と出力してください。
1.1. ソートして比較する
3つの数を昇順に並べてしまえば、(5 5 7) と等しいかどうかの比較一発で判定できます。
(defun go-shichi-go-p (a b c)
(equal (sort (list a b c) #'<)
'(5 5 7)))
(defun solve ()
(let* ((a (read))
(b (read))
(c (read)))
(princ (if (go-shichi-go-p a b c) "YES" "NO"))))
#-swank
(solve)Code language: Lisp (lisp)sortはCommon Lispでは破壊的操作ですが、listで新しいリストを作っているので問題ありません。equalはリストの構造と中身を再帰的に比較します。
2. ABC042B – 文字列大好きいろはちゃんイージー
N個の文字列S1、S2、…、SNを辞書順に並べて連結した文字列を出力してください。
B – 文字列大好きいろはちゃんイージー
2.1. sortとformatで一気に片付けられる
(defun solve ()
(let* ((n (read))
(l (read))
(s (loop repeat n collect (read-line))))
(declare (ignore l))
(format t "~{~A~}" (sort s #'string<))))
#-swank
(solve)Code language: Lisp (lisp)string<はCommon Lispの標準関数で、2つの文字列を辞書順で比較します。
第1引数が小さければその先頭の不一致位置（整数）を、そうでなければnilを返す仕様で、sortの述語として自然に使えます。
formatの~{~A~}は、リストの各要素に~Aを適用するループディレクティブです。
区切り文字を指定しないと要素をそのまま連結します。
あと、各文字列の長さLは問題文に登場しますが使わないので、(declare (ignore l))で明示的に無視しています。
3. ABC042C – こだわり者いろはちゃん
整数NとK個の整数D1、D2、…、DKが与えられます。
C – こだわり者いろはちゃん
N以上の整数のうち、10進数表記にD1〜DKのいずれも含まないものの最小値を求めてください。
3.1. 再帰で各桁をチェックする
(defun digits-not-have-p (n d)
(cond ((= n 0) t)
((find (mod n 10) d) nil)
(t (digits-not-have-p (floor n 10) d))))
(defun min-ok (n d)
(loop for result from n
until (digits-not-have-p result d)
finally (return result)))
(defun solve ()
(let* ((n (read))
(k (read))
(d (loop repeat k collect (read))))
(princ (min-ok n d))))
#-swank
(solve)Code language: Lisp (lisp)制約上Nは最大10000、禁止数字も最大9種類なので、そこまでパフォーマンスを意識しないでも十分間に合います。
digits-not-have-pは末尾の桁から順にチェックする再帰関数です。modで最下位桁を取り出し、禁止リストdにfindで探します。findは要素が見つかればその値を、なければnilを返すので、条件分岐に直接使えます。floorで末尾の桁を落とし、nが0になったら全桁クリアです。
loopのuntilは条件が真になった時点でループを終了し、finally節のresultはそのときの値を指しているので、条件を満たした最初の整数がそのまま返ります。