atcoder-q001-d.clj

atcoder-q001-d.clj

;; AtCoder 過去問 : 001-D 【レースゲーム】
;; http://arc001.contest.atcoder.jp/tasks/arc001_4

(defn- read-input
  []
  (letfn [(read-num-pair
            [] (->> (clojure.string/split (read-line) #"\s+")
                    (map #(Long/parseLong %))))
          (read-num-pairs
            [n] (repeatedly n read-num-pair))]
    (let [N (Long/parseLong (read-line))
          [[x0 xn] & coll] (read-num-pairs (inc N))]
      [N x0 xn (rest (map list (range) coll))])))

(defn- search-path
  [N x0 xn pss]
  (let [[path & _] (reduce (fn [[acc xa ya da :as v] [y [xl xr]]]
                             (let [dl (- xl xn)]
                               (if (> dl da)
                                 [(conj acc [xl y]), xl y dl]
                                 (let [dr (- xr xn)]
                                   (if (< dr da)
                                     [(conj acc [xr y]), xr y dr]
                                     v)))))
                           [[[x0 0]] x0 0 (- x0 xn)]
                           pss)]
    (conj path [xn N])))

(defn- calc-length
  [path]
  (->> (partition 2 1 path)
       (reduce (fn [acc [[x1 y1] [x2 y2]]]
                 (let [dx (- x1 x2)
                       dy (- y1 y2)]
                   (+ acc (Math/sqrt (double (+ (* dx dx) (* dy dy)))))))
               0.0)))
(defn q001-d
  []
  (println  (->> (read-input)
                 (apply search-path)
                 calc-length)))

;; ------------------------------------------
;; 以下動作確認用
;; ------------------------------------------
(defn run-test
  [f & args]
  (with-in-str (apply str (interpose "\n" args))
    (f)))

(do
  (println "【出力1】")
  (run-test q001-d
            "7"
            "3 3"
            "2 5"
            "4 6"
            "2 3"
            "3 6"
            "3 4"
            "4 6"
            "2 5"
            "1 5")
  (println "\n【出力2】")
  (run-test q001-d
            "5"
            "3 3"
            "0 5"
            "0 5"
            "0 5"
            "0 5"
            "0 5"
            "0 5"))

;; ------------------------------------------
;; 結果
;; ------------------------------------------
;; 【出力1】
;; 8.22677276241436

;; 【出力2】
;; 5.0