Code Jam Japan むずかしー

Posted by YpsilonTAKAI On 2011年10月2日日曜日 0 コメント

今日は環境を調えて、6時間みっちり Code Jam やりました。

結局 AとBのSmallだけしか時間内にできなかった。
Cの問題はそれほど時間がかからなそうだったけど、順番に解くのにこだわりたくて、でも、結局だめだったけど。
時間切れ後に、いちおう、CのSmallも解いてみた。

次回は、1つぐらいLargeが解けるようになっていたい。


問題が公開されているんで、一応僕の書いたコードを。



あら。 Gistって修正すると、貼ったやつも変っちゃうんだね。便利なような不便なような。
Gistベースで修正してるので、随時更新されます。
前のを見たい人は、下の方のリンクからGistに直接アクセスしてくださいです(10/7)


問題Aです。
最初は書いてあるとおりに解いた。Smallだと数秒で解ける。
修正版は、Largeでも250ms程度で解けた。 完了。


(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


問題Bです。
最初からいちおうしらみつぶしでないやりかたを模索した。
現在修正中。

(require '[clojure.contrib.io :as io])
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Main funcs
;; sort coffee data by
;; : in descending order with satisfaction
;; : and in accending order with expiry date.
(defn sort-coffee-data [dat-list]
(sort (fn [d1 d2]
(cond (> (last d1) (last d2)) -1
(< (last d1) (last d2)) 1
:else (if (< (second d1) (second d2)) -1 1)))
dat-list))
(defn asign-coffee [coffee-dat K]
(let [[num due wgt] coffee-dat
P (if (> due K) K due)
n (if (> num P) P num)]
[(* wgt n) P n]))
(defn update-coffee-list [coffee-list P n]
(map (fn [[num due wgt]]
[num
(cond (> due P) (- due n)
(> due (- P n)) (- P n)
:else due)
wgt])
coffee-list))
(defn gcj-pB [key-arg coffee-list]
(let [[_ K] key-arg]
(loop [coffee-list (sort-coffee-data coffee-list)
total-days K
s-total 0]
(if (empty? coffee-list)
s-total
(let [[s-amount P n] (asign-coffee (first coffee-list) K)]
(recur (update-coffee-list (next coffee-list) P n)
(- K n)
(+ s-total s-amount)))))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Support funcs
;; get args from the question file.
;; returns them as
;; ((1 ((N K) ((c1 t1 s1)(c1 t1 s12)...))) (2 ........))
(defn get-gcj-args-list-pB [file-name]
(let [tmptmp
(reduce (fn [[tmp-dat res] dat]
(cond (= (count dat) 2) [[dat []] (conj res tmp-dat)]
(= (count dat) 3) [[(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)))))
(defn gcj-get-ans-pB [file-name f]
(map (fn [[num args]] [num (apply f args)])
(get-gcj-args-list-pB file-name)))
(defn gcj-create-ans-pB [in-file out-file f]
(with-open [bw (io/writer out-file)]
(io/with-out-writer bw
(dorun
(for [[num ans] (gcj-get-ans-pB in-file f)]
(println (str "Case #" num ": " ans)))))))
;; (time (gcj-create-ans-pB "B-large-practice.in" "B-large-practice.out" gcj-pB))
;; time for large
;; "Elapsed time: 535.676461 msecs"
view raw gcjj_pB.clj hosted with ❤ by GitHub

問題 C。
時間切れ後に解いた。 問題のとおり。でも、Small解くのに1分半くらいかかってしまう。
そのうち修正。


(require '[clojure.contrib.io :as io])
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Main funcs
;; find digits pair for a and b
;; returns [<total bit count> <carry>]
(defn check-one-digit [tgt-digit carry is-msb]
(if (zero? carry)
(if (zero? tgt-digit)
[2 1] ;; carry 0, digit 0 -> 1 1
[1 0]) ;; carry 0, digit 1 -> 1 0
(if (zero? tgt-digit)
[1 1] ;; carry 1, digit 0 -> 1 0
(if is-msb
[0 0] ;; carry 1, digit 1, msb yes -> 0 0
[2 1]))));; carry 1, digit 1, msb no -> 1 1
;; Get last digit
(defn lsb [n]
(rem n 2))
;; Top digit or not
(defn msb? [n]
(= n 1))
;; Main func
(defn gcj-pC [n]
(loop [tgt-n n
bit-count 0
carry 0]
(if (zero? tgt-n)
bit-count
(let [[bits carr] (check-one-digit (lsb tgt-n) carry (msb? tgt-n))]
(recur (bit-shift-right tgt-n)
(+ bit-count bits)
carr)))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Support funcs
;; get args from the question file.
;; returns them as
;; ((1 N1) (2 N2) ........))
(defn get-gcj-args-list [file-name]
(map list
(iterate inc 1)
(map (fn [line-dat]
(map (fn [s] (BigInteger. s))
(.split line-dat " ")))
(drop 1 (io/read-lines file-name)))))
(defn gcj-get-ans [file-name f]
(pmap (fn [[num args]] [num (apply f args)])
(get-gcj-args-list file-name)))
;; Get answer : for 1 line data
(defn gcj-create-ans [in-file out-file f]
(with-open [bw (io/writer out-file)]
(io/with-out-writer bw
(dorun
(for [[num ans] (gcj-get-ans in-file f)]
(println (str "Case #" num ": " ans)))))))
;;(gcj-create-ans "C-large-practice.in" "C-large_practice.out" gcj-pC)
;; "Elapsed time: 67.20944 msecs"
view raw gcjj_pC.clj hosted with ❤ by GitHub
ラベル: ,

0 コメント:

コメントを投稿