Introduction

ブログ内検索

  • このサイトの記事を検索 by Google

おすすめの一冊!

無料ブログはココログ

« ぐりもん on Google Chrome | トップページ | TopCoder 連載第1回の問題 »

2010-02-07

TopCoder の「探索」

土曜日の朝、Twitter を眺めていると、@chokudai さんが
TopCoder の記事を書かれたというお話をされていました。


  ⇒ トップクラスだけが知る「このアルゴリズムがすごい」
    --  探索」基礎最速マスター
     --  最強最強アルゴリズマー養成講座
      --  ITmedia


さっそく記事を開いてみると、TopCoder の問題が掲載されてます。


  ⇒ 問題 (SRM456 Div1Medium/Div2Hard)



一見しただけだと難しさがわからなかったのですが、
ちょっと考えてみると、

 ・cut の回数が膨大 (~1,000,000,000) なので、
  できた切片をそのままリストとかで保持すると爆発。

 ・というか、この回数でバックトラック探索とかしたら
  いつまでたっても終わらない。

というわけで、なかなか奥が深そう。




で、気がつけばお昼・・・。なんと4時間もかかりました><

いろいろ試行錯誤した結果、なんとか自力で解けました。

書いてみた Common Lisp のコードは以下のとおり:


;; TopCorder (SRM456 Div1Medium/Div2Hard)
;; http://www.itmedia.co.jp/enterprise/articles/1002/06/news001_3.html
; 
; ※ "k" は 問題より1小さいモノとする(問題は「1ベース」だが「0ベース」で解く)。
;
; 0~k番目までのすべての棒が同じ長さであるのが最適解。それに近づけることを目指す。
; 計算過程において、k>=n のときは「長さ0の棒」があると仮定して処理すればよい。
; 計算過程において、cは十分大きいと仮定して良い(期待より小さいときに打ち切られてもそれが最善解である)。
; 計算過程において、k番目以降の棒の存在は無視してよい。
;
; カットした部分はすべて同じ長さ。それ以外の長さのモノは高々50本しかない。
; よって「カウンタ」と「リスト」で別々に管理する。
;

(defun insert-stick (elem list)
  (if (null list)
      (list elem)
      (let ((pos (position elem list :test #'>=)))
        (cond
         ((null pos) (append list (list elem)))
         ((= pos 0) (cons elem list))
         (t (append (subseq list 0 pos) (cons elem (nthcdr pos list))))))))

(defun cut-stick (length sticks)
  (if (or (null sticks) (< (car sticks) length))
      (values sticks nil)
      (values
       (cond ((< (car sticks) length) sticks)
             ((= (car sticks) length) (cdr sticks))
             ((> (car sticks) (* 2 length))
              (insert-stick (+ length (mod (car sticks) length)) (cdr sticks)))
             (t (insert-stick (- (car sticks) length) (cdr sticks))))
       t)))

(defun try-cut (length sticks) ; ある長さ以上の棒が何本作れるか
  (reduce #'(lambda (acc sample)
              (+ acc (floor (/ sample length))))
          (cons 0 sticks)))

(defun trial (k sticks)
  (labels ((rec (upper-bound lower-bound)
;             (format t "~A ~A~%" upper-bound lower-bound) ; for debug
             (if (= (- upper-bound lower-bound) 1)
                 lower-bound
                 (let* ((length (+ lower-bound (ceiling (/ (- upper-bound lower-bound) 2))))
                        (num (try-cut length sticks)))
                   (if (<= num k)
                       (rec length lower-bound)
                       (rec upper-bound length))))))
    (rec (1+ (car sticks)) 1))) ; ←ほんとは初期値は「最初の k 本の平均」とかにすべき

(defun div2hard (k c sticks)
  (let ((n (length sticks)))
    (cond
     ((= c 0) (nth k sticks))
     ((= k 0) (div2hard k (1- c) sticks))
     (t
      (let* ((length (trial k sticks))
             (count (min c (try-cut length sticks))))
        (block cutting
          (dotimes (i c i)
            (multiple-value-bind (s cont) (cut-stick length sticks)
              (if (not cont)
                  (return-from cutting nil))
              (setf sticks s))))
        (let ((pos (position length sticks :test #'>=)))
;          (format t "~A ~A ~A~%" sticks count k) ; for debug
          (if (null pos)
              (if (< k count)
                  length
                  (or (nth (- k count) sticks) 0))
              (cond
               ((< k pos) (nth k sticks))
               ((< k (+ pos count)) length)
               (t (or (nth (- k count) sticks) 0))))))))))

(defun sample-test (list c k)
  (div2hard (1- k) c (sort list #'>)))
とりあえず Cygwin 上の clisp.exe に喰わせれば動きます。 ちなみに、「棒の長さは整数」と思いこんで解いてしまったので、 記事の回答とは微妙に動作が違っています^^; この問題、最初から「ちからわざ」で探索しようとしても破綻してしまい、 ちょっと気がつけばキレイに解ける、という、良い問題だと思いました。 さすがは TopCoder です。 でも、手強かった・・・。 この連載の他の回でも TopCoder の問題が紹介されてるみたいなので、 時間があるときにトライしてみようと思います~

« ぐりもん on Google Chrome | トップページ | TopCoder 連載第1回の問題 »