柵の修理問題 Fence Repair Problem

3253 -- Fence Repairという問題をやってみるテスト。

問題

農家のJohnが農場の柵を修繕しようと計画したところ、L1, L2, ..., LNの長さをもつN枚の板が必要だと分かった。
彼は、L1からLNまでの総和に等しい長さの板を一枚買い、それをノコギリで切り分けることにした。
しかし、ノコギリを持っていないことに気づいたので、知りあいの農家Donにノコギリを貸してくれるよう打診した。
資本家でもあるDonはノコギリを貸さず、自分が板を切る作業をN-1回行う代わりに各回ごとに料金を請求したいと提案した。各回の料金とは、そのときに切断する板の長さと同じ。すなわち、長さ21の板を板に切り分ける場合は21となる。
この料金の考え方に従うと、板を切る順番によって最終的な請求額が変化する。Johnが支払うべき最小の金額を求めよ。

解くための考え方

例として長さ 21 の板から長さ 8, 5, 8 の3つの板に分ける場合を考えると、次の二通りの分け方がある。

1. まず 13 と 8 に分け、次に長さ 13 の板を 8 と 5 に分ける。
2. まず 16 と 5 に分け、次に長さ 16 の板を 8 と 8 に分ける。

これを図示したのが次の図。1番目の料金が 21 + 13 = 34 となり、2番目は 21 + 16 = 37 となるので、1番目のほうが安く上がる。

大雑把な分析だが、図はデータ構造で言うところの二分木の形になり、木の下のほうに短い板があったほうが全体のコストが小さくなる。したがって、問題を解くためには、N枚の板の中からできるだけ短い板を集めながらボトムアップに木を構築していけばよい。その様子を示したのが下図。

短い板を優先して集めるので、これも「貪欲法」のアルゴリズムと言える。また、木の構成方法が「ハフマン符号化法」で使う「ハフマン木」と同じになっている。ただし、この問題ではコストの合計値が分かればよいので、木を完全に構成する必要はない。

コードと実行例（Emacs Lisp で）

入力として L1, L2, ..., LN をリストで渡すと、結果（最小の料金）を返すような関数にした。

(defun fence-repair (lst)
  "メインの関数です"
  (cond
   ((null lst) 0)
   ((= (length lst) 2) (apply '+ lst))
   (t
    (multiple-value-bind (pos-min pos-next-min)
        (position-smallest-two lst)
      (let ((sum (+ (nth pos-min lst) (nth pos-next-min lst))))
        (+ sum
           (fence-repair
            (remove-nth
             pos-min
             (replace lst (list sum) :start1 pos-next-min) ))))))))

(defun remove-nth (n list)
  "リストからn番目の要素を消す"
  (if (zerop n)
      (cdr list)
    (cons (car list) (remove-nth (1- n) (cdr list)))))

(defun position-smallest-two (list)
  "最小値をもつ要素と、2番目に小さい値をもつ要素の位置を返す"
  (let* ((min 0) (next-min 1) (n (length list)) (i 1))
    (while (< i n)
      (cond
       ((< (nth i list) (nth min list))
        (setf next-min min) (setf min i) )
       ((< (nth i list) (nth next-min list))
        (setf next-min i) ))
      (incf i) )
    (list min next-min) ))

以下は実行例で、それぞれ (8, 5, 8) と (1 1 2 2 3 3) の場合。

(fence-repair '(8 5 8))
=> 34

(fence-repair '(1 1 2 2 3 3))
=> 30
;;おそらく以下のような二分木になるはず (+ 12 7 5 4 2) で 30
       12
    7      5
   4  3   2  3
 2   2
1  1

今度はハフマン符号化のプログラムをELispで作ってみたい。SICPにヒントが載ってるし。

参考

• 3253 -- Fence Repair
• Fence Repair(PKU No.3253) - kanetaiの二次記憶装置
• Amazon.co.jp： プログラミングコンテストチャレンジブック: 秋葉 拓哉, 岩田 陽一, 北川 宜稔: 本