以前に時間切れになった問題を解き直しました。
1. D – Nutrients
sumsに、各栄養素を足していって、すべて満たしたところで終了しています。
(defun read-fixnums (N)
(declare (type fixnum N))
(loop with vec = (make-array N :element-type 'fixnum)
for i below N
do (setf (aref vec i) (read))
finally (return vec)))
(defun print-yesno (c)
(princ (if c "Yes" "No")))
(defun satisfy-all-nutrients (M eatens necessities)
(loop for j below M
always (>= (aref eatens j) (aref necessities j))))
(defun main ()
(let* ((N (read))
(M (read))
(Am (read-fixnums M)))
(loop repeat N
with sums = (make-array M
:element-type 'fixnum
:initial-element 0)
do (loop for i below M
do (incf (aref sums i) (read)))
until (satisfy-all-nutrients M sums Am)
finally (print-yesno (satisfy-all-nutrients M sums Am)))))
#-swank(main)
Code language: Lisp (lisp)
2. E – Upgrade Required（TLE20）
まずは、素朴に回答しました。
;; (defparameter *vec* #(1 2 3 4 5 6 7 8))
;; (update-versions-num! *vec* 2 6) ;=> 2
;; *vec* ; => #(6 6 3 4 5 6 7 8)
(defun update-versions-num! (vec x y)
(loop for i below (length vec)
with cnt = 0
when (<= (aref vec i) x)
do (setf (aref vec i) y)
(incf cnt)
finally (return cnt)))
(defun main ()
(let* ((N (read))
(Q (read))
(vec (coerce (loop for i from 1 to N collect i)
'vector)))
(loop repeat Q
do (print (update-versions-num! vec (read) (read))))))
#-swank(main)Code language: Lisp (lisp)サンプルはクリアしましたが、時間切れ 20。
制約条件が 2≤N≤106 で、1≤Q≤2×105 なので、流石にまともに操作していると時間が足りません。
2.1. 数値ごとの個数を記録する（TLE 9）
この問題では、必ずしもすべての数値を記録する必要はなさそうです。
操作の過程でどんどん上のバージョンにまとまっていくからです。
ただ、x -> y というバージョンアップで、途中のものが残ってしまうので、注意が必要です。
今回は、下限から x までの個数を y に足すことで計算しました。
;; (defparameter *m* (make-memo 8))
;; #(0 1 1 1 1 1 1 1 1)
;; (update-versions-num/2! *m* 1 2 6)
;;=> 2
;; #(0 0 0 1 1 1 3 1 1)
(defun update-versions-num/2! (memo min x y)
(loop for i from min to x
with result = 0
do (incf result (aref memo i))
(setf (aref memo i) 0)
finally (progn
(incf (aref memo y) result)
(return result))))
(defun make-memo (n)
(let ((v (make-array (1+ n) :element-type 'fixnum
:initial-element 1)))
(setf (aref v 0) 0)
v))
(defun main/2 ()
(let* ((N (read))
(Q (read)))
(loop repeat Q
with memo = (make-memo N)
with min = 1
for x = (read)
for y = (read)
do (print (update-versions-num/2! memo min x y))
(setf min x))))
#-swank(main/2)Code language: Lisp (lisp)少し改善しましたが、まだ時間切れが9つあります。
2.2. min の更新条件を直した（AC）
チェックをスキップできる下限（min）の更新を間違えていました。
常に x を入れていたのですが、最小になるように更新する必要がありました。
(when (> x min)
(setf min x))Code language: Lisp (lisp)これで、時間内に解けました。
完成コードは、
;; (defparameter *m* (make-memo 8))
;; #(0 1 1 1 1 1 1 1 1)
;; (update-versions-num/2! *m* 1 2 6)
;;=> 2
;; #(0 0 0 1 1 1 3 1 1)
(defun make-memo (n)
(let ((v (make-array (1+ n) :element-type 'fixnum
:initial-element 1)))
(setf (aref v 0) 0)
v))
(defun update-versions-num/2! (memo min x y)
(loop for i from min to x
with result = 0
do (incf result (aref memo i))
(setf (aref memo i) 0)
finally (progn
(incf (aref memo y) result)
(return result))))
(defun main/2 ()
(let* ((N (read))
(Q (read)))
(loop repeat Q
with memo = (make-memo N)
with min = 1
for x = (read)
for y = (read)
do (print (update-versions-num/2! memo min x y))
(when (> x min)
(setf min x)))))
#-swank(main/2)Code language: Lisp (lisp)2.3. 【考察】過去の操作履歴から計算する（WA 19）
なかなか更新条件の方法のミスに気づかず、過去の操作履歴から、アップデートする台数を計算する方法も考えていました。
事前に何も操作していなければ、 x → y に操作するとき、単に x 台アップデートします。
しかし、事前に xi > x となる xi があれば、すでに操作する台数は 0 です。
xi < x かつ yi > x の場合は、x 台から xi を減らさないといけません。
逆に、xi < x かつ yi < x なら、今回のアップデートでは無視してよいです。
つまり、yi > x となる最大のxi を求め、(x-xi)がクエリの答えのはずです。
(defun update-versions-num/ht! (ht min x y)
(cond
((<= x min) 0)
(t (loop for xi being each hash-key of ht
using (hash-value yi)
with result = x
when (and (< xi x)
(> yi x))
do (setf result (min result
(- x xi)))
when (< xi min)
collect xi into to-remove
finally (progn
(setf (gethash x ht) y)
(loop for i in to-remove
do (remhash i ht))
(return result))))))
(defun main/ht ()
(let* ((N (read))
(Q (read)))
(declare (ignore N))
(loop repeat Q
with ht = (make-hash-table)
with min = 1
for x = (read)
for y = (read)
do (print (update-versions-num/ht! ht min x y))
(setf min (max x min)))))
#-swank(main/ht)Code language: Lisp (lisp)ところが、不正解が19です。
実は、このアプローチは、「xi < x かつ yi > x の場合は、x 台から xi を減らす」という部分に問題がありました。
というのも、操作を繰り返していくと、バージョン xi 以下の台数は、xi 台とは限らなくなっていくのです。
最初はバージョン i のPCがちょうど1台ずつあるので、「バージョン xi 以下は xi 台」が成立しています。
しかし操作を重ねると、あるバージョンに複数台が集まったり、空のバージョンが生まれたりします。
なので、この方法ではうまくいきませんでした。