Code Jam Japan 問題B 解いた

Posted by TAKAIY On 2011年11月11日金曜日 0 コメント

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パターンあるのでそれぞれ、やりかたを考えて対応する。

これでアルゴリズムの基本が決ったので、境界条件とか考えてコーディング。


・ sort-coffee-data
コーヒーのリストを優先度の高い順に並べ変える。
 - 満足度の高いものが前
 - 満足度が同じなら、残りの数の多いものが前 (この条件いらないけど)

・ asign-coffee
K日の期間で、指定のコーヒーをどれだけ飲めるかを計算する。
返るのは、満足度の合計、上記のP、上記のn


・update-coffee-list
残っているコーヒーのリストの賞味期限を変更する。
上記の2枚目のロジックを実装している。


・gcj-pB
解答作成本体。 
ソートしたコーヒーのリストの先頭から1つずつ、期間K日で飲めるものを決定していきながら、Kとリストのアップデートを繰り返す。 リストがなくなったら終り。
繰り返しごとに計算される満足度はs-amountに積算。

他の関数は、問題と解答の入出力関連。

かかった時間は入出力込みで、535.676461 msecs。


0 コメント:

コメントを投稿