AtCoder Grand Contest 040 B - Two Contests

本番では考察不足で2ペナを出しましたが…自分の考察がある程度整理できたので書きます。

解法

公式解説にならい、それぞれのコンテストを「集合」、問題 $i$ を解ける人の範囲を「区間 $i$ 」、コンテストの楽しさを「含まれる区間の共通部分の長さ」と書くことにします。区間を半開区間として扱うことで区間 $\lbrack s, t)$ の長さを単に $t-s$ と書けるので、区間は半開区間として扱います。また区間の番号は $i = 0, ..., N-1$ で表記します。

2つの集合を集合1, 2と書くことにします。このとき集合 $k$ に含まれる区間の共通部分は（もし存在するならば）区間になり、その左端は含まれる区間の $L_{i}$ の最大値、右端は $R_{i}$ の最小値となります。これらの値をそれぞれ $s_{k}, t_{k}$ と書くことにします。共通部分が存在しない場合のことも考慮すると、この共通部分の長さは $\max(t_{k} - s_{k}, 0)$ と計算できます。

$N$ 個の区間を左端 $L_{i}$ でソートして、番号を振り直してみましょう。このとき $L_{i}$ が最も大きい区間 $N-1$ が含まれるほうを集合2、そうでないほうを集合1と呼ぶことにします。

ここで「集合1に含まれる区間のうち、最も番号が大きいものはどれか」を全探索しましょう。これを $x$ 番目とすると、以下の状態まで割り振りが確定します。

f:id:betrue12:20191104045925p:plain

ここまで割り振ると、残りの区間の $L_{i}$ は $L_{x}$ 以下なので、 $s_{1} = L_{x}, s_{2} = L_{N-1}$ であることが確定します。このように左端でソートして、それぞれの集合で左端が大きいものを1つ決めてあげることで、 $s_{k}$ の値が確定して考えやすくなります。

$t_{1}, t_{2}$ については今後区間が足されることで小さくなるかもしれませんが、既に割り振っている $R_{i}$ の最小値を暫定値と思っておきましょう。

残りの区間はどう割り振るべきでしょうか？このとき実は、残っている区間を集合1, 2のどちらか一方に全て入れるケースだけを考えれば良いです。残っている区間の中で最も小さい $R_{i}$ はどちらかの集合に割り振らなければならず、これを割り振ったほうにそれより大きい $R_{i}$ を割り振っても影響はないので、どちらか一方の集合に集中させたほうが $t_{1}, t_{2}$ への損失は少ないからです。

つまり、割り振りは以下の2パターンになります。

f:id:betrue12:20191104045934p:plain

f:id:betrue12:20191104045943p:plain

これは結局、区間の割り振り方としては「ある1つの区間 $x$ だけを孤立させて残りを全部まとめる」か、「左端ソートして、ある区間 $x$ を境界として二分する」かのどちらかしか考えなくても良いということを意味しています。

これはどちらも、 $L_{i}$ の範囲最小値と $R_{i}$ の範囲最大値を効率的に求められるようにしておけば計算できます。セグメント木、スパーステーブルが使えますし、今回必要なのは左右端からの範囲だけなので累積min/maxを前計算しても良いです。 $\log$ を乗せてもいいならセグメント木が楽だと思います。