fixedpoint.jp - Get Many Persimmon Trees (2009-11-15)

すぐに思いつく generate and test 式のアルゴリズム(グリッドの面積と矩形の面積の積のオーダー)は、用意されているデータセット(B1.txt)については十分に実行可能です。特に C や C++ で実装すれば十分に速いです。

もっと効率のよいアルゴリズムを考えると、木の本数と矩形の面積の積のオーダーになります:

#!r6rs

(import (rnrs))

(let loop ((total (read)))
  (if (zero? total)
      (exit)
      (let* ((width (read))
             (height (read))
             (coords-x (make-vector total))
             (coords-y (make-vector total)))
        (do ((k 0 (+ k 1)))
            ((= k total))
          (vector-set! coords-x k (- (read) 1))
          (vector-set! coords-y k (- (read) 1))) ; 0-based
        (let* ((w (read))
               (h (read)))
          (let ((ht (make-eqv-hashtable total)))
            (do ((k 0 (+ k 1)))
                ((= k total))
              (let* ((i (vector-ref coords-x k))
                     (j (vector-ref coords-y k)))
                (let ((y0 (min (+ j h) height)))
                  (do ((y j (+ y 1)))
                      ((= y y0))
                    (let ((x0 (min (+ i w) width)))
                      (do ((x i (+ x 1)))
                          ((= x x0))
                        (let* ((n (+ (* y width) x))
                               (u (hashtable-ref ht n 0)))
                          (hashtable-set! ht n (+ u 1)))))))))
            (let-values (((_ v) (hashtable-entries ht)))
              (display (apply max (vector->list v)))
              (newline))))
        (loop (read)))))

手元のノートPC(CPU 1.6GHz)で計測してみると、Ypsilon r503 では1秒強で実行できます。ikarus 0.0.3 では eqv-hashtable が実装されておらず実行できませんでした。MzScheme 4.2.1 では5秒前後。Mosh r2180 ではなぜか処理途中でハングしました。