G - Longest Chord Chain Editorial
by 
MMNMM
公式解説の考察（適当な点で円周を切り開いたときに互いに包含関係にある \(k\) 個の弦を残せる \(\iff\) 答えが \(k\) 以上）を前提とします。
区間の集合 \(\lbrace I _ 1,I _ 2,\ldots,I _ k\rbrace\) が \(I _ 1\subset I _ 2\subset\cdots\subset I _ k\) を満たしていることを、単調番号付け可能であると呼ぶことにします。
与えられる \(N\) 本の弦を \((a _ i,b _ i)\ (1\leq a _ i\lt b _ i\leq2N)\) とします。 区間の集合 \(\lbrace\lbrack a _ i,b _ i\rbrack\rbrace\cup\lbrace\lbrack b _ i,a _ i+2N\rbrack\rbrace\) の単調番号付け可能な部分集合の大きさの最大値を求めればよいです。
証明
まず、答えがこの最大値以上であることを示します。
大きさ \(k\) の単調番号付け可能な部分集合 \(\lbrace I _ 1,I _ 2,\ldots,I _ k\rbrace\) を考えます。 どの区間の長さも \(2N\) 未満なので、\(x,x+2N\) のいずれも最大の区間 \(I _ k\) に含まれない実数 \(x\ (0\leq x\lt2N)\) が存在します。実数 \(x\) に対応する円周上の点（具体的には、\(x\) が整数なら対応する点、\(x\) が整数でないなら \(n\lt x\lt n+1\) なる \(n\) について点 \(n\) と点 \(n+1\) の間（ただし、便宜上点 \(2N+1\) と書いて点 \(1\) を表すこととします）の適当な点を取ればよいです）で円周を切り開くことで、区間に対応する \(k\) 個の弦が条件を満たすことがわかります。 よって、答えが \(k\) 以上であることがわかります。
逆に、答えの値以上の大きさを持つ単調番号付け可能な部分集合が存在することを示します。
条件を満たす \(k\) 個の弦について、切り開く点を \(1\) つ選びます（ \(2\) つありますが、どちらを選んでも議論に支障はありません）。 この点が点 \(i,\) 点 \(i+1\) の間にあるとして、点の番号を切り開く点から円周を時計回りに進んだときに出会う順番に \(i+1,i+2,\ldots,i+2N\) と振り直します。 すると、条件を満たす弦たちは \(\lbrace\lbrack a _ i,b _ i\rbrack\mid i+1 /2\notin\lbrack a _ i,b _ i\rbrack\rbrace\cup\lbrace\lbrack b _ i,a _ i+2N\rbrack\mid i+1 /2\in\lbrack a _ i,b _ i\rbrack\rbrace\) の単調番号付け可能な部分集合に対応することがわかります。 \(\lbrace\lbrack a _ i,b _ i\rbrack\mid i+1 /2\notin\lbrack a _ i,b _ i\rbrack\rbrace\cup\lbrace\lbrack b _ i,a _ i+2N\rbrack\mid i+1 /2\in\lbrack a _ i,b _ i\rbrack\rbrace\) は \(\lbrace\lbrack a _ i,b _ i\rbrack\rbrace\cup\lbrace\lbrack b _ i,a _ i+2N\rbrack\rbrace\) の部分集合なので、示されました。
これは、区間を一方の端でソートし、もう一方の端の値について最長増加（もしくは減少）部分列の長さを求めることで解くことができます。
実装例は以下のようになります。
#include <vector>
#include <algorithm>
#include <iostream>
#include <ranges>
int main() {
using namespace std;
unsigned N;
cin >> N;
vector<pair<unsigned, unsigned>> intervals;
intervals.reserve(2 * N);
for (unsigned i{}, a, b; i < N; ++i) {
cin >> a >> b;
if (a > b)
swap(a, b);
intervals.emplace_back(a, b); // [a, b] と
intervals.emplace_back(b, a + 2 * N); // [b, a + 2N] を追加する
}
// 端の値でソートして
ranges::sort(intervals, greater{}, &pair<unsigned, unsigned>::second);
// LIS を求める
vector<unsigned> lis_dp;
for (const auto l : intervals | views::keys)
if (const auto it{ranges::lower_bound(lis_dp, l)}; it != end(lis_dp))
*it = l;
else
lis_dp.emplace_back(l);
// LIS の長さが答え
cout << size(lis_dp) << endl;
return 0;
}
posted:
last update: