ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Codeforces Hello 2020 D. New Year and Conference

Problem - D - Codeforces

問題概要

講演会において  n 個の講演がある。A会場とB会場の2つがあり、講演  i をA会場で行う場合の講演時間は時刻の閉区間  \lbrack sa_{i}, ea_{i}\rbrack で、B会場で行う場合の講演時間は時刻の閉区間  \lbrack sb_{i}, eb_{i}\rbrack で表される。

2つ以上の講演の集合  s のうち、以下のようなものが存在するかを判定せよ。(存在しない場合に YES、存在する場合に NO を出力せよ)

  •  s に含まれる講演を、ある片方の会場で全て行った場合には講演時間に共有点を持つ2つの講演が存在し、他方の会場で全て行った場合にはそのようなものが存在しない。

制約

  •  1 \le n \le 100000
  • 与えられる各時刻は  1 \le t \le 10^{9} を満たす

解法

上記の問題概要は多少要約しているのでバレバレなのですが、集合  s としてはちょうど2つの講演からなるものだけを考えれば十分です。

会場Aにおいて共有点を持ち、会場Bにおいて共有点を持たない2つの講演が存在するかを調べます。逆も同様に調べます。

会場Aにおける各講演の開始・終了時刻をそれぞれソートし、時刻を順番に進めていくシミュレーションを行います。こうしながら「今見ている時刻を会場Aでの講演時間に含む講演の集合」を管理します。

この集合が変化した各タイミングにおいて、「集合の中に、会場Bの講演時間において共有点を持たないような2つの講演が存在するか?」をチェックします。実際には、講演が終わっただけの時刻では条件を「満たしにくく」なるだけなので、いずれかの講演が始まる時刻についてだけチェックすれば良いです。

これをチェックする方法としては、集合に含まれる講演の会場Bでの開始時刻と終了時刻をそれぞれ多重集合として持っておきます。その開始時刻の最大値を  s_{(B, \max)} 、終了時刻の最小値を  t_{(B, \min)} とすると、会場Bの講演時間において共有点を持たない2つの講演が存在する必要十分条件 t_{(B, \min)} \lt s_{(B, \max)} が成立することです。

これはC++std::multiset など順序付き集合が存在する言語ならそのまま、存在しない言語なら座標圧縮+BIT二分探索や優先度付きキューを工夫して用いる等の方法で求めることができます。

ACコード

Submission #68175586 - Codeforces