ABC207 C - Many Segments 解説
問題
Difficulty : 397 atcoder.jp
解説
$N$ の最大が 2000 と小さいため、組み合わせを全探索しても間に合う。
問題は共通部分の判定である。
区間の種類ごとに場合分けしてもいいのだが、もっと分かりやすくしたい。
複雑になっているのは、「$X$ 以上」や「$Y$ 未満」など、統一性がないことである。
これをどちらかに統一することを考える
「以上」「以下」はその数字を含むため、変換が難しそうに感じる。
一方「大きい」「未満」はその数字を含まないため、値を足し引きすることで「以上」「以下」にすることが容易である。
分かりやすく足し引きする値を 1 としてみる。
区間 $(4,8)$ を変換すると $[5,7]$ となり、元の区間の条件を満たしつつ共通部分を持つかの判定が容易にできる。
共通部分を持つかの判定は、$max(l_i,l_j)≤min(r_i,r_j)$ でできる。
$max(l_i,l_j)>min(r_i,r_j)$ だと、例えば $l_i,r_i,l_j,r_j,$のような順に並んでいる。
小さい $l_i$ と大きい $l_j$ の間に $r_i$ が存在するため、小さい側 $(l_i,r_i)$ と大きい側 $(l_j,r_j)$ で共通部分を持たない別々の区間になってしまう。
つまり、そうでないなら 端点を含むどこかで共通部分ができる。
これで AC と言いたいが、先ほどのように足し引きする値を 1 にした場合、おかしなことになる。
例えば、$(2,3)$ という区間を変換すると $[3,2]$ と明らかにおかしい。
そこで値をもっと下げてみる。
0.1 にすると、$[2.1,2.9]$ となり、条件を満たすし、先ほどのようにおかしなことにもならない。
この値の許容範囲は 0.5 まであり、解説でも 0.5 を扱っている。
以上のことから、区間ごとに決めた値を足し引きし、共通部分を持つか判定することでこの問題を AC できた。
