2018JOI春合宿3-2 Bitaro's Party 解説

問題リンク

解説

小課題は自明なので略

$Y_i=0$ の場合を考えると、トポロジカル順で DP をしてやれば解ける。 データ構造などで処理するのは難しそうなので、$Y_i$ に付随する計算量は、 $Y_i$ の定数倍もしくは小さい別の関数がかかった形にする必要があるだろうという予想がつく。

$Y_i=0$ の場合のように最大値だけを保持することには意味がなく、出発頂点をセットにしても、その頂点がつぶれてしまったら何も前計算がない状態になってしまうので、平方分割の要領で $B$ 個持っておくことにする。

$Y_i>=B$ となるのは高々 $\frac{\sum(y_i)}{B}$ 回なので、このときは愚直に DP をしてやればよい。

このとき、計算量は $O(N+BMlogBM+N\frac{\sum(y_i)}{B})$ になるので、$B=100$ くらいにしてやると通る。