概要

問題特有の性質に着目し，解きやすい形に言い換えて行きましょう．

問題原案：uni_kakurenbo

解説

時系列を考えると，コンテスト $i$ が終了して以降に(直/間接的に)コンテスト $j$ に参加できるとき，必ずコンテスト $j$ が終了して以降に(直/間接的に)コンテスト $i$ に参加することはできないと分かります．

したがって，$1$ 以上 $N$ 以下の整数を頂点とし，「コンテスト $i$ の終了時にコンテスト $j$ に参加できる」ことを $i \to j$ の有向辺で表現したグラフ $G$ は非循環 (DAG) になります．

$G$ の $i \to j$ の辺の重みを，コンテスト $i$ の終了からコンテスト $j$ が始まるまでの待ち時間 $t_j - u_i$ とすると，この問題は以下のように言い換えることができます．

• $G$ の(重みを無視した)最小道被覆の大きさと，その被覆が含む辺の重みの総和の最小値を求めよ．

DAG における最小道被覆問題が，最大二部マッチング問題，すなわち最大流問題に帰着できることは有名ですが，この問題は最小費用流を用いて同様のアプローチで解くことができます．

時間計算量は $O(X^3 \log X)$ などです．

解説：uni_kakurenbo

実装例