ABC165C - Many Requirementsを全探索で解いてみた

40代文系社内SEが、AtCoder Beginner Contest 165 C - Many RequirementsをCommon Lispで解いてみました。

この問題で難しいところは、計算量を求めるところと数列を列挙するところです。

まず、計算量については$2 \le N \le 10$と、$1 \le M \le 10$から、最大$10^10$に見えますが、実はそこまで大きくなりません。数列の条件として昇順に並ぶことが記載されているため、先頭が$10$のときはすべて$10$の1通りになります。
具体的には重複組み合わせを使って数列のパターン数を求めることができ、最大$92378$通りとなります。

次に数列を列挙する処理については、以下のように実装します。

1. 数列の末尾が$M$未満なら加算する
2. 数列の末尾が$M$なら先頭に向かって$M$未満を検索する
3. $M$未満が見つかったらそれを加算し、末尾に向かってコピーする
4. すべてが$M$になったら終了する

毎回終了条件をチェックするので、数列1パターンあたりの計算量は$O(N)$です。

得点の計算を含めた計算量の最大値は$O(92378 \times 10 \times 50)$となり、間に合います。

(let* ((n (read))
       (m (read))
       (q (read))
       (a (make-array q))
       (b (make-array q))
       (c (make-array q))
       (d (make-array q))
       (va (make-array (1+ n) :initial-element 1)))

  ;; a, b, c, dを読み込む
  (loop for i from 0 below q
        do (setf (aref a i) (read)
                 (aref b i) (read)
                 (aref c i) (read)
                 (aref d i) (read)))

  (labels ((score ()
             ;; 得点を計算する
             (loop for i from 0 below q
                   for ai = (aref a i)
                   for bi = (aref b i)
                   for ci = (aref c i)
                   for di = (aref d i)
                   when (= (- (aref va bi) (aref va ai)) ci)
                     sum di)))

    (loop with ans = 0
          while (not (= n (count m va :start 1)))
          do (setf ans (max ans (score)))
             
             (if (< (aref va n) m)
                 (incf (aref va n))
                 
                 ;; 繰り上がり処理
                 (let* ((i (position-if #'(lambda (ai) (< ai m)) va :from-end t))
                        (vai (aref va i)))
                   (loop for j from i to n
                         do (setf (aref va j) (1+ vai)))))
          finally
             (format t "~A~%" (max ans (score))))))
  

解法やアルゴリズムで分類した、解いてみたリストはこちらです。
AtCoder Beginner Contestを解いてみたリスト