Code Jam Japan 問題A 解いた

Posted by YpsilonTAKAI On 2011年10月5日水曜日 0 コメント
Code Jam Japan予選のA問題。当日終ってから考えたロジックを実装してみた。
結果は上でき。 ということで、解説です。




その方法は、逆順でのトレース。
知りたい場所のカードが初めにどこにあったのかを考えるわけ。
図を書いたので、貼りつけ。



ソースはこれ

(require '[clojure.contrib.io :as io])
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Main funcs
;; step back
;; get previous position of the target card
(defn un-shuffle [W ab-list]
(let [[A B] ab-list]
(cond (<= W B) (+ W (- A 1))
(and (> W B)
(<= W (+ B A -1))) (- W B)
:else W)))
;; step back all the way
(defn gcj-pA [key-arg cut-list]
(let [[_ _ W] key-arg]
(loop [rev-cut-list (reverse cut-list)
w W]
(if (empty? rev-cut-list)
w
(recur (next rev-cut-list)
(un-shuffle w (first rev-cut-list)))))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Support funcs
;; get args from the question file.
;; returns them as
;; ((1 ((M T W) ((A1 B1)(A2 B2)...))) (2 ........))
(defn get-gcj-args-list-pA [file-name]
(let [tmptmp
(reduce (fn [[tmp-dat res] dat]
(cond (= (count dat) 3) [[dat []] (conj res tmp-dat)]
(= (count dat) 2) [[(first tmp-dat) (vec (conj (second tmp-dat) dat))] res]
:final (vec (conj (second tmp-dat) dat))))
[[] []]
(map (fn [line-dat]
(map (fn [s] (BigInteger. s))
(.split line-dat " ")))
(drop 1 (io/read-lines file-name))))]
(map list
(iterate inc 1)
(conj (vec (drop 1 (second tmptmp))) (first tmptmp)))))
;; get answar list with answer function f
(defn gcj-get-ans-pA [file-name f]
(pmap (fn [[num args]] [num (apply f args)])
(get-gcj-args-list-pA file-name)))
;; create answar file from question file with answer function f
(defn gcj-create-ans-pA [in-file out-file f]
(with-open [bw (io/writer out-file)]
(io/with-out-writer bw
(dorun
(for [[num ans] (gcj-get-ans-pA in-file f)]
(println (str "Case #" num ": " ans)))))))
;;;;;;;;;;;;;;;;;;;;;;;;;
;; invoke
(time (gcj-create-ans-pA
"A-large-practice.in"
"A-large-practice.out"
gcj-pA))
view raw gcjj_pA.clj hosted with ❤ by GitHub


なんと、1秒以下で答がでた。


ラベル: ,

0 コメント:

コメントを投稿