Code Jam Japan予選のB問題。 ふと思い出したときにちょこっと考えていたりしたんだけど、やりかた思いついたので、やってみた。 解けた。
もうちょっと効率を上げたりできそうだけど、500msちょっとで解けたんだからまあこれでいいでしょう。
予選当日に考えた方式は以下の通り。結果としてこの方式で解いた。
戦略
- 今日何を飲むかではなくて、このコーヒーはいつ飲むのかを考える。
- 満足度の高いコーヒーから飲む日を決めていく。
- 飲む日はどうやって決めるのか？
たとえば
- 期間が5日
- 満足度(S)10 賞味期限(T)が3日のコーヒーAが2杯(C)
- 満足度1 賞味期限が5日のコーヒーBが5杯
の場合、
3日目にコーヒーAが残っていたら飲むのはA
3日目にAを飲む場合、2日目にAが残っていたら飲むのはA
このように、賞味期限の日からさかのぼって埋めていけばむだなく割り当てることができる。
- 他のコーヒーの予定がすでにが入っているときはそこをとばす。
上記のAのコーヒーは、Tが3でCが2なので、3日目と2日目に飲む。
Bのコーヒーは、Tが5でCが5なので、5日目、4日目、3日目と2日目は埋まっているからとばして、あとは1日目に飲む。
当日のアルゴリズム
当日は、これを実現するために、全体の日程を配列にして埋めていく方法を採った。
上記の場合ならこんな感じ。
ooooo
oAAoo
BAABB
実際は、配列の要素には、決定したコーヒーの満足度を入れておいて、最後に全部足して答えとしていました。
でも、この方式でLargeが解けないのは明白。
日数が1兆を超えるような条件では、どんなに小さくしても配列が作れない。
改良版のアルゴリズム
- 日程の情報を持てないので、選んだコーヒーがどれだけ飲めるかを決定するロジックできないかどうか考えることにした。
- あるコーヒーは、T日目からさかのぼってC日間飲める。すでに飲むコーヒーが決っている日はとばす。この「とばす」のをなんとかすればいい。
で、無くしてしまえないかと考えた。
そして、その分期間を減らす。 あと、残っているコーヒーの賞味期限も変更しないといけない。
その方法はこんな感じ。
3パターンあるのでそれぞれ、やりかたを考えて対応する。
これでアルゴリズムの基本が決ったので、境界条件とか考えてコーディング。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (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" |
・ sort-coffee-data
コーヒーのリストを優先度の高い順に並べ変える。
- 満足度の高いものが前
- 満足度が同じなら、残りの数の多いものが前 (この条件いらないけど)
・ asign-coffee
K日の期間で、指定のコーヒーをどれだけ飲めるかを計算する。
返るのは、満足度の合計、上記のP、上記のn
・update-coffee-list
残っているコーヒーのリストの賞味期限を変更する。
上記の2枚目のロジックを実装している。
・gcj-pB
解答作成本体。
ソートしたコーヒーのリストの先頭から1つずつ、期間K日で飲めるものを決定していきながら、Kとリストのアップデートを繰り返す。 リストがなくなったら終り。
繰り返しごとに計算される満足度はs-amountに積算。
他の関数は、問題と解答の入出力関連。
かかった時間は入出力込みで、535.676461 msecs。
0 コメント:
コメントを投稿