【AtCoder ADT】
部分文字列からDP
（E20260513_1）

by

関連記事

1. A – “atcoder”.substr()

subseqのインデックスと問題の数をそろえたら、完成です。

(defun main()
  (let* ((L (read))
         (R (read)))
    (princ (subseq "atcoder" (1- L) R))))

#-swank(main)Code language: Lisp (lisp)
1. A – “atcoder”.substr()

2. B – T-shirt

場合分けで当選確率を計算し、それを浮動小数点数で出力します。

;; (get-probability 30 500 20 103) 2/47
(defun get-probability (a b c x)
  (cond
    ((<= x a) 1)
    ((<= x b) (/ c (- b a)))
    (t 0)))

(defun print-float (d)
  (format t "~f" (float d 0.0d0)))

(defun main ()
  (let* ((a (read))
         (b (read))
         (c (read))
         (x (read)))
    (print-float (get-probability a b c x))))

;; (float 2/47)0.04255319
#-swank(main)Code language: Lisp (lisp)
2. B – T-shirt

3. C – First Query Problem

数列をベクタに変換し、素直にクエリを読み取りながら、値の更新と出力を実行しました。

(defun main ()
  (let* ((N (read))
         (An (coerce (loop repeat N collect (read))
                     'vector))
         (Q (read)))
    (read-do-queries An Q)))

(defun read-do-queries (An Q)
  (loop repeat Q
        for typ = (read)
        for k = (read)
        when (= typ 1)
          do (setf (aref An (1+ k)) (read))
        when (= typ 2)
          do (princ (aref An (1+ k)))
             (terpri)))

#-swank(main)Code language: Lisp (lisp)
3. C – First Query Problem

4. D – A Reverse

部分文字列の反転は、左・中央・右に分割し、中央だけを反転させて結合しました。


;; (subst-reverse 3 7 "abcdefgh") ;=> "abgfedch"
(defun subst-reverse (L R str)
  (let* ((left (subseq str 0 (1- L)))
         (mid (subseq str (1- L) R))
         (right (subseq str R)))
    (concatenate 'string left (reverse mid) right)))

(defun main ()
  (princ (subst-reverse (read) (read) (read-line))))

#-swank(main)Code language: Lisp (lisp)
4. D – A Reverse

ここで時間切れでした。

4. D – A Reverse

5. E – Dice Sum

この問題を素朴に考えると、mnm^n通りの可能性の中から、合計が K 以下のパターンを数えることになります。
一応、メモ化で i 個組み合わせて、sum になる組み合わせを２次元配列に記録しました。

(defparameter *prime* 998244353)

;; (dice-sum-pattern 2 3 4) ;=> 6
(defun dice-sum-pattern (N M K)
  (let ((dp (make-array (list (1+ N) (1+ K))
                        :initial-element nil)))
    (labels ((rec (i sum)
               (setf (aref dp i sum)
                     (cond
                       ((aref dp i sum))
                       ((= i n) (if (<= sum K) 1 0))
                       (t (loop for j from 1 to M
                                when (<= (+ sum j) K)
                                sum (rec (1+ i) (+ sum j)) into s
                                finally (return (mod s *prime*))))))))
      (rec 0 0))))

(defun main ()
  (let* ((n (read))
         (m (read))
         (k (read)))
    (princ (dice-sum-pattern n m k))))

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

そしたら、思いのほか、時間内に解けました。

5. E – Dice Sum

今回は、n の最大値が 50 でコールスタックが尽きなかったからです。

5.1. 考察は別記事へ（包除原理）

ほかには、 K個 の飴を n 人で配るパターン（ただし、一人の最大はm個まで）、として考える方法も思いつきました。
ただ、「m個まで」という制限をどう計算すればよいのか思いつきませんでした。
そこで、誰かが m+1 個以上もらっている組み合わせを考えて引く方法があることを知りました。