第4回 ドワンゴからの挑戦状 予選 D - ディスクの節約
問題文
考察
端的に言うとtayama_killerデス。
嘘解法を1ケースだけ落とすという♰悪魔的行為♰をしている。
さて、見た感じからdpをしたくなる感じ。
局所的にディスク容量が大きくなるところを考えると、あるタスクを行うときにそのタスクが依存しているタスクはディスクに残しておかないといけないというところから、あるタスクと、それが依存するタスクについてを見て行きたくなる。
構造は木になるので、ある点に関して、その子供をどの順番に行っていくか、みたいな感じに考えたくなる。局所的にディスク容量が大きくなるものはなるべくほかのタスクがディスクにない状態で行いたいからね。
ということで、
ある点について、その子供のタスクを行うまでに使う最大ディスク容量を見ていき、それをbitDPで最小値をとっていく
という木DPを再起でやる感じになりそう。
だ～が、これが嘘解法。
木DPで行うと、ある点と、その子供について、一つ子供に関するタスクがすべて終わるまで他のタスクを行わないことになっているが、最適解はこれに限らないのかな？
木構造が作れてしまうと木DPでやりたくなるけれど、こうゆう離散的な値をとるようなものはなるべくすべてのケースを網羅できるようにするべきなんだね。腹立つけれどいい勉強でもあったかな。
ということで、今回は
dp[i] := 立っているタスクまで完了したときの最小の必要最大ディスク容量
で
遷移は状態がiの時、行いたいタスクが依存するタスクがすでに行われていたら
dp[i + (まだ行っていないタスク)]
= max(dp[i], 行うタスクの容量+そのタスクが依存するタスクの容量+その他の残しておくべきタスクの容量)
という感じになりますた。
計算量はO(n^2 * 2^n)ちと遅いね、おそらくnは一個減らせそうな気はしてるけどわからんかった。
