【AtCoder ADT】（easy_20260501_1）

by

関連記事

1. A – AtCoder Quiz 2

find-if で、次のランク得点を求め、nil なら “expert”です。

(defun next-rank-point (x)
  (let ((rank-points '(40 70 90)))
    (find-if #'(lambda (rp) (< x rp)) rank-points)))


(defun main ()
  (let* ((x (read))
	 (next (next-rank-point x)))
    (princ (if next (- next x) "expert"))))

#-swank(main)Code language: Lisp (lisp)
1. A – AtCoder Quiz 2

2. B – A Unique Letter

文字が3つだけなので、一つ一つの文字の出現数を計算しました。
二重ループになるので、文字数が多いときは、もっとよい方法がありそう。

(defun unique-letter (str)
  (loop for ch across str
	when (= 1 (count ch str :test #'char=))
	  do (return ch)
	finally (return nil)))

(defun main ()
  (let* ((s (read-line))
	 (u (unique-letter s)))
    (princ (if u u -1))))
#-swank(main)Code language: Lisp (lisp)
2. B – A Unique Letter

3. C – Broken Rounding

小さい桁から四捨五入すると、ギリギリのときに違いが出てくる問題です。
桁数と10の累乗の値が1ずれるのが、ややこしかったです。

;; (broken-round 2048 2) ;=> 2100
(defun broken-round (x k)
  (loop for i from 0 below k
	do (setf x (round5 x i))
	finally (return x)))

(defun round5 (x k)
  (let* ((ex (expt 10 (1+ k)))
	 (high (floor x ex))
	 (low (mod x ex))
	 )
    (* ex (+ high (if (>= low (/ ex 2)) 1 0)))))

(defun main ()
  (let* ((x (read))
	 (k (read)))
    (print (broken-round x k))))

#-swank(main)Code language: Lisp (lisp)
3. C – Broken Rounding

4. D – typo(WA1)

同じ文字は飛ばして、隣同士が入れ替えになっている場所を探しました。

;; (typo-p "type" "tyep") ; => T
;; (typo-p "type" "tpey") ; => NIL
(defun typo-p (ss tt)
  (loop for i from 0 below (1- (length ss))
	for cs = (aref ss i)
	for ct = (aref tt i)
	  thereis (and (char/= cs ct)
		       (char= cs (aref tt (1+ i)))
		       (char= ct (aref ss (1+ i))))))


;; (yesno t) ;=> "Yes"
(defun yesno (c)
  (declare (type boolean))
  (if c "Yes" "No"))

(defun main ()
  (let* ((ss (read-line))
	 (tt (read-line)))
    (yesno
     (cond ((equal ss tt))
	   (t (typo-p ss tt))))))
#-swank(main)Code language: Lisp (lisp)

ところが、1問不正解に。

4. D – typo(WA1)

4.1. コード

まず、間違えの一つは、最後の文字の処理です。
read-lineで読み取った文字列の最後に空白文字が含まれていたので、それを取り除きます。

(defun trim-last-whitespace (str)
  (string-right-trim '(#\space) str))Code language: Lisp (lisp)

次は、typo-pの判定です。
先ほどは、thereisで一文字反転があるかを判定していましたが、判定した以降を見逃していました。
そこで、そもそも違う文字の数 diff を数えて、それが2であることを確認する必要がありました。

(defun diff (ss tt)
  (loop for cs across ss
	for ct across tt
	count (char/= cs ct)))

(defun typo-p (ss tt)
  (loop for i from 0 below (1- (length ss))
	for cs = (aref ss i)
	for ct = (aref tt i)
	count (and (char/= cs ct)
		   (char= cs (aref tt (1+ i)))
		   (char= ct (aref ss (1+ i)))) into typo
	finally (return (and (= typo 1) (= (diff ss tt) 2)))))Code language: Lisp (lisp)

二重にループを回して非効率なのですが、とりあえずは正解になりました。

4.1. コード

ここで時間切れでした。

4.1. コード

5. E – Bingo 2(TLE28)

まずは、素直にグリッドを作って、数値が出てくれば -1 を記録し、行・列・対角線ですべて -1 になっているかを確認しました。

(defun make-bingo-grid (N)
  (let ((grid (make-array (list N N) :element-type 'fixnum)))
    (loop for i below N
	  do (loop for j below N
		   do (setf (aref grid i j)
			    (+ (* N i) (1+ j))))
	  finally (return grid))))

(defun mark (N grid A)
  (let ((val (1- A)))
    (setf (aref grid
		(floor val N) (mod val N))
	  -1) ))

(defun bingo-p (N grid)
  (or 
   (loop for i below N
	   thereis (loop for j below N
			 always (= (aref grid i j) -1)))
   (loop for i below N
	   thereis (loop for j below N
			 always (= (aref grid j i) -1)))
   (loop for i below N
	 always (= (aref grid i i) -1))
   (loop for i below N
	 always (= (aref grid (- N i 1) i) -1))))

;; (mark-bingo 3 '(5 1 8 9 7)) ;=> 4
;; (mark-bingo 3 '(4 2 9 7 5)) ;=> -1
;; (mark-bingo 4 '(13 9 6 5 2 7 16 14 8 3 10 11)) ;=> 9
(defun mark-bingo (N An)
  (let ((grid (make-bingo-grid N)))
    (loop for a in An
	  for turn from 1
	  do (mark N grid a)
	  when (bingo-p N grid)
	    do (return turn)
	  finally (return -1))))

(defun main ()
  (let* ((N (read))
	 (TT (read))
	 (An (loop repeat TT collect (read)))
	 )
    (princ (mark-bingo N An))))
#-swank(main)Code language: Lisp (lisp)

さすがに、ループが多すぎて時間切れ。

5. E – Bingo 2(TLE28)

5.1. 行・列で該当数をカウントするようにした(WA2)

毎回、グリッドをカウントするのは無駄が多いので、行[N]・列[N]・対角線[2]ごとに出現数をカウントすることにしました。

;; (destructive) mark and check whether count == N
(defun mark-bingo-count-p (N A col-dp row-dp diagonal-dp)
  (let* ((val (1- A))
	 (row (floor val N))
	 (col (mod val N)))
    (cond ((= N (incf (aref row-dp row))))
	  ((= N (incf (aref col-dp col))))
	  ((= row col)
	   (= N (incf (aref diagonal-dp 0))))
	  ((= (- N row 1) col)
	   (= N (incf (aref diagonal-dp 1)))))))

(defun make-dp (N)
  (make-array N :element-type 'fixnum :initial-element 0))

;; (mark-bingo/2 3 '(5 1 8 9 7)) ;=> 4
;; (mark-bingo/2 3 '(4 2 9 7 5)) ;=> -1
;; (mark-bingo/2 4 '(13 9 6 5 2 7 16 14 8 3 10 11)) ;=> 9
(defun mark-bingo/2 (N An)
  (let* ((row-dp (make-dp N))
	 (col-dp (make-dp N))
	 (diagonal-dp (make-dp 2)))
    (loop for A in An
	  for turn from 1
	  when (mark-bingo-count-p N A row-dp col-dp diagonal-dp)
	    do (return turn)
	  finally (return -1))))

(defun main ()
  (let* ((N (read))
	 (TT (read))
	 (An (loop repeat TT collect (read))))
    (princ (mark-bingo/2 N An))))
#-swank(main)
Code language: Lisp (lisp)

まだ、2問不正解。
境界条件のチェックが甘いようです。

5.1. 行・列で該当数をカウントするようにした(WA2)

5.2. 対角線の中心

この cond の条件分岐に問題があることがわかりました。

condは、条件式のあとに値がないと、そのまま真偽値を返します。
ただ、途中の条件式が t だと残りの条件は判定されません。
ここで、row == col をそのまま条件式にしていたので、row == col かつ (N-row-1) == col のケースに、後半がカウントされていませんでした。

;; mark-bingo-count-p
(cond ((= N (incf (aref row-dp row))))
	  ((= N (incf (aref col-dp col))))
	  ((= row col)
	   (= N (incf (aref diagonal-dp 0))))
	  ((= (- N row 1) col)
	   (= N (incf (aref diagonal-dp 1)))))Code language: Lisp (lisp)

これを修正すると、

;; (destructive) mark and check whether count == N
(defun mark-bingo-count-p (N A col-dp row-dp diagonal-dp)
  (let* ((val (1- A))
	 (row (floor val N))
	 (col (mod val N)))
    (cond ((= N (incf (aref row-dp row))))
	  ((= N (incf (aref col-dp col))))
	  ((and (= row col)
		(= N (incf (aref diagonal-dp 0)))))
	  ((and (= (- N row 1) col)
		(= N (incf (aref diagonal-dp 1))))))))Code language: JavaScript (javascript)
5.2. 対角線の中心

完成したコードは、

;; (destructive) mark and check whether count == N
(defun mark-bingo-count-p (N A col-dp row-dp diagonal-dp)
  (let* ((val (1- A))
	 (row (floor val N))
	 (col (mod val N)))
    (cond ((= N (incf (aref row-dp row))))
	  ((= N (incf (aref col-dp col))))
	  ((and (= row col)
		(= N (incf (aref diagonal-dp 0)))))
	  ((and (= (- N row 1) col)
		(= N (incf (aref diagonal-dp 1))))))))

(defun make-dp (N)
  (make-array N :element-type 'fixnum :initial-element 0))

;; (mark-bingo/2 3 '(5 1 8 9 7)) ;=> 4
;; (mark-bingo/2 3 '(4 2 9 7 5)) ;=> -1
;; (mark-bingo/2 4 '(13 9 6 5 2 7 16 14 8 3 10 11)) ;=> 9
(defun mark-bingo/2 (N An)
  (let* ((row-dp (make-dp N))
	 (col-dp (make-dp N))
	 (diagonal-dp (make-dp 2)))
    (loop for A in An
	  for turn from 1
	  when (mark-bingo-count-p N A row-dp col-dp diagonal-dp)
	    do (return turn)
	  finally (return -1))))

(defun main ()
  (let* ((N (read))
	 (TT (read))
	 (An (loop repeat TT collect (read))))
    (princ (mark-bingo/2 N An))))
#-swank(main)Code language: PHP (php)

全問正解まで、約2時間かかりました。

5.2. 対角線の中心