Educational Codeforces Round 92 F. Bicolored Segments

お題箱より。

Problem - F - Codeforces

問題概要

$n$ 個の閉区間 $\lbrack l_{i}, r_{i}\rbrack$ が与えられ、それぞれは赤または青のいずれか1色に塗られている。

「異なる色の2つの区間が共有点を持ってはいけない」という条件のもとで、これらのうちできるだけ多くの区間を選びたい。選ぶ個数の最大値を求めよ。

制約

$1 \le n \le 2\times 10^{5}$
$1 \le l_{i} \le r_{i} \le 10^{9}$

解法1：DP

あらかじめ区間を右端でソートしておき、右端の値が小さいものから順に見ていくDPを考えます。インデックスもソート後の順番で振り直します。

赤の区間を採用できる条件は、これまで最後に採用した青の区間の右端が、採用しようとしている赤の区間の左端よりも小さいことです。逆も然りです。なので素直に考えると、

$dp\lbrack i\rbrack\lbrack j\rbrack =$ これまで最後に採用した赤の区間が $i$ で、最後に採用した青の区間が $j$ であるときの、採用した区間数の最大値

というDPを構成することができます。区間を1-indexedで扱い、「まだその色の区間を採用していない」をインデックス $0$ で表すと都合が良いです。これで計算量 $O(n^{2})$ では解けますが、間に合いません。

ではどうするのかというと、さらに状態をまとめます。以下のように2色それぞれで状態をまとめ、区間を順番に見ていきながら同時に更新していきます。

$dp_{1}\lbrack i\rbrack =$ 今までに見た区間だけを使って、最後に採用した赤の区間が $i$ であるときの、採用した区間数の最大値
$dp_{2}\lbrack i\rbrack =$ 今までに見た区間だけを使って、最後に採用した青の区間が $i$ であるときの、採用した区間数の最大値

これは先ほどの $dp\lbrack i\rbrack\lbrack j\rbrack$ という2次元テーブルで管理していた状態について、それぞれの軸方向ごとに最大値を取ったものになります。このDPテーブルをどのように更新するのか考えます。

まず2次元テーブルを用いたDPがどのような遷移になるのか確認しましょう。見ようとしている区間が赤だとします。更新対象となるのは、最後に採用した青の区間の右端が見ようとしている赤の区間の左端よりも小さいものです。つまり $j$ がある値以下の範囲で更新が行われることになり、図で表すと以下のようになります。

f:id:betrue12:20200801153434p:plain

これを両軸方向に串刺しにして最大値を取った $dp_{1}, dp_{2}$ はどうなるでしょうか。図のインデックスを用いて説明します。まず $dp_{2}$ について考えると、更新対象となっている $dp_{2}\lbrack 0\rbrack, dp_{2}\lbrack 1\rbrack$ をそれぞれ $1$ 増やせば良いことが分かります。そして $dp_{1}\lbrack 3 \rbrack$ は増やした後のこれらの値の最大値になります。

つまり2次元テーブルで状態を管理しなくても、これらの $dp_{1}, dp_{2}$ だけで遷移を計算することができます。全ての区間を見終わったら、 $dp_{1}, dp_{2}$ のどちらか（どちらでもOK）について最大値を取ったものが答えになります。

必要な操作は区間への加算と区間の最大値取得なので、遅延伝播セグメント木などで実現することができます。

ACコード1

Submission #88638709 - Codeforces

解法2：二部グラフ

公式解説で解説されている方法です。

各区間を頂点とみなし、同時に採用してはいけない区間の間に辺を結ぶグラフを考えると、これは二部グラフになります。求めたいのはこのグラフの最大独立集合の頂点数です。

二部グラフでは最大独立集合の頂点数は全頂点数から最大マッチングの数を引いたものになります。つまり最大マッチングを求めれば答えを計算できます。

参考：二部グラフの最小点被覆、最大安定集合 (最大独立集合)、最小辺被覆を総整理！ - Qiita

ということで結局、赤と青の区間の組で共有点を持つものをなるべく多くマッチングさせることを考えれば良いです。これは例えば以下のように求めることができます。

赤の区間の左端と青の区間の右端を混ぜてソートする。値が同じ場合、赤の区間のほうが前になるようにする。
区間を順番に見ていきながら以下の処理を行う。
- 赤の区間の場合は、「マッチング待ち区間」として右端をプールする。
- 青の区間の場合は、プールされているマッチング待ち区間であって共有点を持つ（つまり右端が青の区間の左端以上である）もののうち、最も右端が小さいものを取り出しマッチングする。