Y箱

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日間飲める。すでに飲むコーヒーが決っている日はとばす。この「とばす」のをなんとかすればいい。

で、無くしてしまえないかと考えた。

とばすのではなくて、決った日を取りのぞいてしまう。
そして、その分期間を減らす。 あと、残っているコーヒーの賞味期限も変更しないといけない。
その方法はこんな感じ。