問題

考え方

まずは最小値に単調性があるので、最小値 $x$ を二分探索することにしよう。つまり以下の問題を考える。ディスク使用量をコストと呼ぶこととする。

「最小値を $x$ とするとき、タスクを実行する過程でコストが $x$ を超えないように、1番目のタスクが実行可能な状態にすることができるかどうか？」

$1 \le N \le 20$ という制約も参考になるかもしれないが、過程の状態のタスク集合は必ずしも連結とは限らない。解説で示されている例がその一つの例である。

なので、木ではなく、bitでタスクの状態を管理することとする。bitの状態を全探索しよう。あるタスクを実行するのに依存がないタスクから実行できることになる。まずはタスク $x_i$ を実行するのに必要なタスク集合を bit で表す。

bit の状態遷移は以下を考える。

このようにして状態を遷移させたときにコスト $x$ を超えずにタスク1 が実行可能な状態集合を取りうることができればOK。そうでなければNGである。計算量は $O(2^N * logN)$ 。なおJavaだと二分探索の最大値をちょうど最大になるようにしないと通らない。

タスクの集合は非連結になりうるので木DPではうまくいかない。bitの集合を全探索しようという気持ちになると解ける。