【AtCoder Daily】
loop・文字コード・ハッシュ表を
使う
（adt_easy_20260420_1）

by

関連記事

1. 問題A（ABC252A） ASCII code

1.1. code-charで文字コードを得る

(defun main ()
  (princ (code-char (read))))

#-swank(main)Code language: Lisp (lisp)
1.1. code-charで文字コードを得る

2. 問題B（ABC311A）First ABC

2.1. 全条件を満たすまで繰り返す（loop … until）

(defun solve (str)
  (loop for i from 0 to (length str)
	for ch across str
	with a = nil
	with b = nil
	with c = nil
	until (and a b c)
	do (cond ((eql ch #\A) (setf a t))
		 ((eql ch #\B) (setf b t))
		 ((eql ch #\C) (setf c t)))
	finally (return i)))

(defun main ()
  (let* ((n (read))
	 (str (read-line)))
    (declare (ignore n))
    (princ (solve str))))

#-swank(main)Code language: Lisp (lisp)
2.1. 全条件を満たすまで繰り返す（loop … until）

3. 問題C（ABC212B） Weak Password

3.1. 隣接する要素の比較（分配束縛）

まずは、シンプルに2つの条件を分けてチェックしました。
loopの分配束縛を使うと、比較を簡潔に書けます。

;; (same4 '(1 1 1 1)) ;=> T
;; (same4 '(1 1 1 2)) ;=> NIL
(defun same4 (xs)
  (loop for (a b) on xs
	while b
	always (= a b)))

;; (next4 '(1 2 3 4)) ;=> T
;; (next4 '(8 9 0 1)) ;=> T
;; (next4 '(8 9 0 0)) ;=> NIL
(defun next4 (xs)
  (loop for (a b) on xs
	while b
	always (cond ((= a 9) (= b 0))
		     (t (= b (1+ a))))))Code language: Lisp (lisp)

あと、文字コードを数値に変換する関数 char-num を用意しました。

;; (char-num #\3) ;=> 3
;; (char-num #\a) ;=> NIL
(defun char-num (ch)
  (when (digit-char-p ch)
    (- (char-code ch) (char-code #\0))))

(defun main ()
  (let* ((xs (loop repeat 4
		   collect (char-num (read-char)))))
    (princ (cond ((same4 xs) "Weak")
		 ((next4 xs) "Weak")
		 (t "Strong")))))

#-swank(main)Code language: Lisp (lisp)
3.1. 隣接する要素の比較（分配束縛）

4. 問題D（ABC409B） Citation

4.1. ハッシュテーブルで頻度表を作る（WA16）

ハッシュテーブルで頻度表を作り、そのキーを数列として降順にチェックしました。

(defun freq-hash (lst)
  (let* ((ht (make-hash-table)))
    (loop for a in lst
	  do (incf (gethash a ht 0))
	  finally (return ht))))

;; (citation '(1 6 2 10 2 3 2)) ;=> 3
(defun citation (lst)
  (let* ((ht (freq-hash lst))
	 (nums (loop for v being the hash-key of ht
		     collect v)))
    (loop for x in (sort nums #'>)
	  with acc = 0
	  do (progn (incf acc (gethash x ht))
		    (when (>= acc x) (return x))))))


(defun main ()
  (let* ((n (read))
	 (lst (loop repeat n collect (read))))
    (princ (citation lst))))

#-swank(main)Code language: Lisp (lisp)
4.1. ハッシュテーブルで頻度表を作る（WA16）

4.2. 答えがAnにあるとは限らない（WA12）

見落とししている条件が2つあることに気づきました。

一つは、条件にあう x がAnから見つからなかったときに、NILを返してしまうこと（終了）。
あと、Anに含まれる数以外で x < acc を満たすことがあること（事前にチェック）。

;; (citation '(1 6 2 10 2 3 2)) ;=> 3
;; (citation '(5 5 5 5))        ;=> 0
(defun citation (lst)
  (let* ((ht (freq-hash lst))
	 (nums (loop for v being the hash-key of ht
		     collect v)))
    (loop for x in (sort nums #'>)
	  with acc = 0
	  do (progn
	       (when (< x acc) (return acc))
	       (incf acc (gethash x ht))
	       (when (>= acc x) (return x)))
	  finally (return 0))))Code language: Lisp (lisp)
4.2. 答えがAnにあるとは限らない（WA12）

4.3. コード（AC）

条件のチェックに見落としがありました。
条件にあう x がAnから見つからなかったときに 0 を返していたのですが、accの値の数になったところで条件を満たすことになります。

;; (citation '(1 6 2 10 2 3 2)) ;=> 3
;; (citation '(5 5 5 5))        ;=> 4
(defun citation (lst)
  (let* ((ht (freq-hash lst))
	 (nums (loop for v being the hash-key of ht
		     collect v)))
    (loop for x in (sort nums #'>)
	  with acc = 0
	  do (progn
	       (when (< x acc) (return acc))
	       (incf acc (gethash x ht))
	       (when (>= acc x) (return x)))
	  finally (return acc))))Code language: Lisp (lisp)
4.3. コード（AC）

Dは時間切れになってしまいましたが、なんとか完成しました。

4.3. コード（AC）