ダイヤグラム（第2回WUPC [H]）

概要

問題文 → ■
公式解説 → なさそう？
自分の提出 → ■

区間 $[L_{i}, R_{i})$ が $M$ 個与えられて、それぞれ選ぶ・選ばないで $2^{M}$ 通りの選択肢があります。すべての点が $2$ 枚以上の区間に被覆されるような選び方を数え上げる問題です。

区間を $L$ 昇順でソートしておいて、その順に区間を置くかどうか決めていくことを考えます。

区間 $[L, R)$ を置く時点では、 $[0, L)$ 部分が $2$ 枚以上の区間に覆われている必要があります。その条件のもと、区間 $[L, R)$ を置いた直後の状態は、ある $a, b$ に対して

が成り立ちます。実際、 $x < L$ の部分は $2$ 枚以上で覆われてということでした。これまで置いた区間はすべて左端が $L$ 以下であるため、 $x ≧ L$ 部分の被覆枚数は $x$ について単調減少です。

この状態 $(a, b)$ に対する数え上げを $dp [a, b]$ として、ひとつずつ区間を置く・置かない場合の遷移を計算していくことにより、本問題は（ソート $O (M \log M)$ 時間を除き） $O (M N^{2})$ 時間で解くことができます。

$N$ の制約が大きいですが、はじめに座標圧縮しておくことで、 $N = O (M)$ の場合に帰着できます。したがって、座標圧縮後に上述の dp を計算することで、本問題は $O (M^{3})$ 時間で解くことができます。