【AtCoder ADT】
インデックス整理と幅優先探索
（easy_20260429_1）

by
  • AtCoder ADT easy_20260429_1のA〜E問題をCommon Lispで解きました。
  • A問題は剰余演算の1-indexed変換、B問題は文字列末尾からのTLD抽出、C問題は重複を避けた組み合わせの数え上げで解きました。
  • D問題はループでインデックスを走査する拡張ABC文字列判定、E問題はキューを使った幅優先探索でウイルス感染をシミュレーションしています。

関連記事

1. A – Last Card

N人で1巡するので割った余りなのですが、たとえば、K=1, A=1 なら、最後にカードを受け取った人は 1 です。
Aから(K-1)人分、次に進みます。
あと、問題文では番号が1起算で1 〜 N番なのに対して剰余だと 0 〜 (N-1)になります。
この辺りの頭の整理が大変です。

;; (last-card 3 3 2) ;=> 1
;; if the card is 1 then A is the last one.
(defun last-card (N K A)
  (1+ (mod (+ (1- A) (1- K)) N)))

(defun main ()
  (princ (last-card (read) (read) (read))))

#-swank(main)Code language: Lisp (lisp)
1. A – Last Card

2. B – TLD

これは、position関数の:from-endキーを使えば、subseqで部分文字列をすぐに取得できました。

(defun top-level-domain (str)
  (let ((pos (position #\. str :from-end t)))
    (subseq str (1+ pos))))

(defun main ()
  (princ (top-level-domain (read-line))))

#-swank(main)Code language: Lisp (lisp)
2. B – TLD

3. C – How many?

同じ数字の再計算を避けるために、a b c は小さい順になるように取り、count-patternで組み合わせ数にしてカウントしました。

(defun ok-p (SS TT a b c)
  (and (<= (+ a b c) SS)
       (<= (* a b c) TT)))

;; (count-pattern 4 2 2) ;=> 2
(defun count-pattern (a b c)
  (cond ((= a b c) 1)
	((or (= a b) (= b c) (= c a)) 3)
	(t (* 3 2))))

(defun solve (ss tt)
  (loop for a from 0 to ss
	sum (loop for b from a to ss
		  sum (loop for c from b to ss
			    when (ok-p ss tt a b c)
			      sum (count-pattern a b c)))))

(defun main ()
  (princ (solve (read) (read))))

#-swank(main)
Code language: Lisp (lisp)
3. C – How many?

4. D – Extended ABC

この問題もはじめは positionで位置を探したのですが、AやBが連続すること、そして1文字もない場合でも許容されることから、ループで条件に合う間をインデックスを回し続ける方法にしました。
最終的なインデックスと文字列の長さが同じなら、ちょうど最後で止まったことになり、「ABC拡張文字列」と言えますし、長さ未満なら不成立です。

;;  (extended-abc-tail-pos "AABCCCAB") ;=> 6
(defun extended-abc-tail-pos (str)
  (loop for ch across "ABC"
	with pos = 0
	do (loop while (and (< pos (length str))
			    (eql ch (char str pos)))
		 do (incf pos))
	finally (return pos)))

(defun yesno (c)
  (declare (type boolean))
  (if c "Yes" "No"))

(defun solve (str)
  (yesno (= (extended-abc-tail-pos str) (length str))))

(defun main ()
  (princ (solve (read-line))))

#-swank(main)Code language: Lisp (lisp)
4. D – Extended ABC

5. E – Virus

それぞれの人の位置は、ドットリストで記録し、

まずは、ある人から次に感染する人のリストを作ることにしました。
ただし、そのときにすでに感染している人は dp に記録して、再計算を避けるようにしています。

新しく感染した人は、queue（というか実際にはスタック）に追加して、次の感染者を確認します。
これを、queueが空になるまで進めます。
queueの初期値には、0番の人を入れています。

;; (infect-p 1 '(1 . 2) '(2 . 2)) ;=> T
;; (infect-p 2 '(1 . 2) '(3 . 2)) ;=> T
(defun infect-p (D p1 p2)
  (<= (+ (square-difference (car p1) (car p2))
	 (square-difference (cdr p1) (cdr p2)))
      (* D D)))

(defun square-difference (x y)
  (* (- x y) (- x y)))

;; dp[i] ... already infected = t
;; ps[i] ... vector of (x . y)
(defun new-infect-from (D ps idx dp)
  (loop for p2 across ps
	for j from 0
	with p1 = (aref ps idx)
	when (and (not (aref dp j))
		  (infect-p D p1 p2))
	  collect j))

;; queue ... list of index who is newly infected.
;; return .. dp[i], vector of infected or not.
(defun infected (N D ps queue)
  (loop while queue
	with dp = (make-array N :element-type 'boolean
				   :initial-element nil)
	with i
	do (setf i (pop queue))
	   (setf (aref dp i) t)
	   (let ((additional (new-infect-from D ps i dp)))
	     (loop for j in additional
		   do (setf (aref dp j) t)
		      (push j queue)))
	finally (return dp)))


(defun yesno (c)
  (declare (type boolean))
  (if c "Yes" "No"))

(defun main ()
  (let* ((N (read))
	 (D (read))
	 (ps (loop repeat N
		   collect (cons (read) (read)) into lst
		   finally (return (coerce lst 'vector))))
	 (queue '(0))
	 (infected-dp (infected N D ps queue)))
    (loop for bool across infected-dp
	  do (princ (yesno bool))
	     (terpri))))
#-swank(main)Code language: Lisp (lisp)
5. E – Virus

E問題は、時間内には解答できず、42分オーバーでした。

5. E – Virus
5. E – Virus
5. E – Virus