B - Meetings 解説
by 
square1001
はじめに
この問題では色々なアプローチがありますが、解法を自然に思いつける方法として、Hall の結婚定理を使ったものを紹介します。
Hall の結婚定理 二部グラフ \(G = (U, V, E)\) に \(U\) の頂点をすべて使うマッチングが存在する必要十分条件は、任意の \(S \subseteq U\) に対して \(\left|N(S)\right| \geq \left|S\right|\) が成り立つことである。
元の問題に戻ってみると、すべての会議に出席できるかという問題は、以下のようにマッチングの問題として考えることができます。
方法 頂点集合を \(U = \{a_1, \dots, a_N\}, V = \{b_0, \dots, b_{179\,999}\}\) とし、各 \(i = 1, \dots, N\) に対して、辺 \((a_i, b_{L_i}), \dots, (a_i, b_{R_i-1})\) を追加したグラフ \(G\) を考える。このグラフに \(U\) の頂点をすべて使うマッチングが存在すれば、すべての会議に出席できる。
Hall の結婚定理の適用
時刻 \(l\) から時刻 \(r\) までの会議に出席するときに、会議 \(1, \dots, N\) にすべて出席できるか、を判定することを考えましょう。ただし、\(l < \min(R_1, \dots, R_N), \ r > \max(L_1, \dots, L_N)\) と仮定します。このとき、会議 \(i\) は時刻 \(\max(L_i, l)\) から時刻 \(\min(R_i, r)\) まで行われるとみなせます。
会議の部分集合 \(S \subseteq \{1, \dots, N\}\) であって、ひとつの会議にでも含まれている時間帯 \(N(S)\) が \(\left|N(S)\right| < \left|S\right|\) を満たすものを考えます（このとき、すべての会議には出席できません）。
ここで \(N(S)\) は区間になると考えてよいです。もし区間でなければ、\(N(S)\) は区間 \(N(T_1), \dots, N(T_k)\) に分けることができ、そのいずれかで \(\left|N(T_i)\right| < \left|T_i\right|\) を満たすためです。すると、\(N(S)\) は以下の \(4\) パターンに分類できます。
- ケース 1: \(l, r-1 \notin N(S)\) の場合
- \(S\) に含まれる会議はすべて時刻 \(l+1\) から時刻 \(r-1\) までに行われるので、それらの会議は「時刻 \(l\) から時刻 \(r\) の会議に出席する」という制限に影響しません。
- よってこのケースになり得るのは、仮に \(l = -\infty, r = +\infty\) だったとしても、すべての会議には出席できない場合です。
- ケース 2: \(l \in N(S), r-1 \notin N(S)\) の場合
- \(S\) に含まれる会議の開始時刻がもし全部 \(l\) だったとしても、\(N(S)\) は変わらないので、\(\left|N(S)\right| < \left|S\right|\) であることも変わりません。
- よってこのケースになり得るのは、仮に \(L_1 = \dots = L_N = -\infty\) だったとしても、時刻 \(l\) 以降だけではすべての会議に出席できない場合です。
- ケース 3: \(l \notin N(S), r-1 \in N(S)\) の場合
- ケース 2 と同様です。このケースになり得るのは、仮に \(R_1 = \dots = R_N = +\infty\) だったとしても、時刻 \(r\) 以前だけではすべての会議に出席できない場合です。
- ケース 4: \(l, r-1 \in N(S)\) の場合
- \(\left|N(S)\right| = r-l\) なので、このケースになり得るのは、\(r-l < N\) となる（\(N\) 未満の長さの時間で \(N\) 個の会議には出席できない）場合です。
まとめると、\(N\) 個の会議すべてに参加できないのは、以下の条件のいずれかを満たすときです。
- 仮に \(l = -\infty, r = +\infty\) だとしてもすべての会議には出席できない。
- 仮に \(L_1 = \dots = L_N = -\infty\) だとして、最初の会議を始める時刻として可能な最も遅い時刻を \(A\) とする。このとき、\(l > A\) である。
- 仮に \(R_1 = \dots = R_N = +\infty\) だとして、最後の会議を終える時刻として可能な最も早い時刻を \(B\) とする。このとき、\(r < B\) である。
- \(r - l < N\) である。
したがって、そもそもすべての会議に出席できない場合は答えは Impossible（ケース 1 に該当）、それ以外の場合は \(A, B\) を計算したうえで答えが
- \(B - A \geq N\) のとき、\(l = A, r = B\) とするのが最適
- \(B - A < N\) のとき、\(l = B-N, r = B\) とするのが最適
と求まります。
高速化パート 1:「すべての会議に出席できるか」を高速に求める
会議 \(1, \dots, N\) にすべて出席できるかどうかは、参加できる会議があればその中で終了時刻が最も早い会議に参加する、という貪欲法で判定できます。優先度付きキューを使うことで、計算量 \(O(N \log N)\) で判定できます。
実際には、各 \(k = 1, \dots, N\) に対して会議 \(1, \dots, k\) にすべて出席できるかを判定する必要があります。どこまでの会議に参加できるかは、\(k\) に関する二分探索で求まるので、計算量 \(O(N \log^2 N)\) で分かります。
高速化パート 2: \(A, B\) を高速に求める
実際には、各 \(k = 1, \dots, N\) に対して会議 \(1, \dots, k\) に参加できるときの答えを求める必要があります。そのため、各 \(k\) に対して \(A, B\) の値を求めなければなりません。ここでは、\(A\) の値、すなわち以下の問題の答えを求めることを考えます（\(B\) の値も同様の方法で求まります）。
問題 会議 \(1, \dots, N\) はそれぞれ時刻 \(R_1, \dots, R_N\) まで行われる。各 \(k = 1, \dots, N\) に対して、以下の問いに答えよ。
- 会議 \(1, \dots, k\) に参加するとき、最初の会議を始める時刻として可能な最も遅い時刻はいつであるか？
終了時刻が早い会議から順に参加するのが最適であることを鑑みると、答えは \(x \geq \min(R_1, \dots, R_k)\) に対する「\(x - (R_i \leq x \ \text{となる会議の個数})\)」の最小値として求まります。よって、各 \(k\) に対しての答えは以下のアルゴリズムで求まります。
- \((a_0, \dots, a_{180000}) = (0, \dots, 180000)\) とする。\(a_x\) は現時点での「\(x - (R_i \leq x \ \text{となる会議の個数})\)」を表す。
- \(k = 1, \dots, N\) に対して、以下を行う。
- \(a_{R_k}, \dots, a_{180000}\) を \(1\) 減少させる
- \(\min(R_1, \dots, R_k) \leq x \leq 180000\) に対する \(a_x\) の最小値が答え（\(A\) の値）
これは遅延評価セグメント木を使うことで計算量 \(O(N \log N)\) で実現できます。
実装例
投稿日時:
最終更新: