【AtCoder ABC214C】
Distribution
（Common Lisp）

by

関連記事

1. 問題

2. 動的計画法で部分最適化を解いた（WA15）

まずは、動的計画法の考え方で、一つ前の人のタイミングを元に計算し、メモ化しておくことにしました。

(defun ith-time (ith Sn Tn dp)
  (declare (type fixnum ith)
	   (type (array fixnum (*)) Sn Tn)
	   (type vector dp))
  (when (>= ith 1)
    (setf (aref dp (1- ith))
	  (cond ((aref dp (1- ith)))
		((= ith 1) (aref Tn 0))
		(t (min (+ (ith-time (1- ith) Sn Tn dp)
			   (aref Sn (- ith 2)))
			(aref Tn (1- ith))))))))

(defun list->nums (lst)
  (make-array (length lst) :element-type 'fixnum
			   :initial-contents lst))

(defun main ()
  (let* ((N (read))
	 (Sn (list->nums (loop repeat N collect (read))))
	 (Tn (list->nums (loop repeat N collect (read))))
	 (dp (make-array N :initial-element nil)))
    (loop for i from 1 to N
	  do (format t "~a~%" (ith-time i Sn Tn dp)))))

#-swank(main)Code language: Lisp (lisp)

結果は、誤答15。

2. 動的計画法で部分最適化を解いた（WA15）

3. 誰が本当の「一人目」なのか？

ここで、「ただし、(N+1) 番目のすぬけ君とは 1 番目のすぬけ君のことを指すとします。」という条件を使えていないのが気になりました。

暗黙のうちに「1 人目が最初」だと考えて、「初期状態」としていましたが、そうでもないことがあるのです。
自分の場所で宝石を受け取る前に、N番目の人から受け取る場合があります。

(defun cycle1toN (i n)
  (1+ (mod (1- i) n)))

(defun ith-time/loop (i N Sn Tn dp)
  (declare (type fixnum i N)
	   (type (array fixnum (*)) Sn Tn)
	   (type vector dp))
  (let* ((ith (cycle1ton i N))
	 (prev (cycle1ton (1- i) N)))
    (setf (aref dp (1- ith))
	  (cond ((aref dp (1- ith)))
		(t (min (+ (ith-time/loop prev N Sn Tn dp)
			   (aref Sn (1- prev)))
			(aref Tn (1- ith))))))))Code language: Lisp (lisp)

配列インデックスの(1- ith)と前の人のprevを区別するのが、ちょっとややこしかったです。
この ith-time/loop関数では、初期状態としていた ((= ith 1) (aref Tn 0)) は消えるので、そのままだと終了しません。

そこで、事前に DP表に書き込んでおく必要があります。
このとき、「初期状態」とすべき人は Tn が最小の人、ということになり、そこから1巡させます。

まずは、Tnの最小の人を探して、その人のタイミングは Tn に等しいことを初期状態とします。

;; (minimum-index #(3 5 2 4 9 10 2)) ;=> 2
(defun minimum-index (vec)
  (let ((minimum (reduce #'min vec))) 
    (loop for idx below (length vec)
	  for n across vec
	  when (= minimum n)
	    do (return idx))))

(defun main ()
  (let* ((N (read))
	 (Sn (list->nums (loop repeat N collect (read))))
	 (Tn (list->nums (loop repeat N collect (read))))
	 (dp (make-array N :initial-element nil))
	 (first (1+ (minimum-index Tn))))
    (loop repeat N
	  for i from first
	  initially (setf (aref dp (1- first))
			  (aref Tn (1- first)))
	  do (ith-time/loop i N Sn Tn dp))
    (loop for i from 1 to N
	  do (format t "~a~%" (ith-time/loop i N Sn Tn dp)))))Code language: Lisp (lisp)

これにより、無事に解くことができました。

3. 誰が本当の「一人目」なのか？

3.1. コード全体

(defun cycle1toN (i n)
  (1+ (mod (1- i) n)))

(defun ith-time/loop (i N Sn Tn dp)
  (declare (type fixnum i N)
	   (type (array fixnum (*)) Sn Tn)
	   (type vector dp))
  (let* ((ith (cycle1ton i N))
	 (prev (cycle1ton (1- i) N)))
    (setf (aref dp (1- ith))
	  (cond ((aref dp (1- ith)))
		((= ith 1) (aref Tn 0))
		(t (min (+ (ith-time/loop prev N Sn Tn dp)
			   (aref Sn (1- prev)))
			(aref Tn (1- ith))))))))

(defun list->nums (lst)
  (make-array (length lst) :element-type 'fixnum
			   :initial-contents lst))
;; (minimum-index #(3 5 2 4 9 10 2)) ;=> 2
(defun minimum-index (vec)
  (let ((minimum (reduce #'min vec))) 
    (loop for idx below (length vec)
	  for n across vec
	  when (= minimum n)
	    do (return idx))))

(defun main ()
  (let* ((N (read))
	 (Sn (list->nums (loop repeat N collect (read))))
	 (Tn (list->nums (loop repeat N collect (read))))
	 (dp (make-array N :initial-element nil))
	 (first (1+ (minimum-index Tn))))
    (loop repeat N
	  for i from first
	  do (ith-time/loop i N Sn Tn dp))
    (loop for i from 1 to N
	  do (format t "~a~%" (ith-time/loop i N Sn Tn dp)))))

#-swank(main)
Code language: Lisp (lisp)
3.1. コード全体