E - Chords Editorial by yuto1115
解説以下、一般性を失わず \(A_i < B_i\) を仮定します。
まず、以下の図のように円環を点 \(1,2N\) の間で切り開いて直線にすることを考えます。元々弦であったものは、元々円環であった直線の上に曲線として描きます。
ここで、元々の円環において弦同士の交点が存在することと、上図右のような切り開いた状態で曲線同士の交点が存在することは同値です(証明略)。よって、切り開いた状態で考えることで問題の見通しがよくなります。弦同士の交点を考える問題においては、この切り開くというアイデアは頻出です。
では、切り開いた状態における曲線同士の交点の存在判定について考えましょう。まず、曲線同士の交点が存在しないことは、\(A_i < A_j < B_i < B_j\) を満たす \(i,j\ (i\neq j)\) が存在しない(*)ことと同値です。これを平衡二分木や segment tree 等を用いて \(O(N\log N)\) で判定することもできますが、ここではスタックを用いて \(O(N)\) で判定するアルゴリズムを紹介します。
- 空のスタック \(S\) を用意する。
- \(j=1,2,\dots,2N\) の順に以下を行う。
- 点 \(j\) がある曲線の左端、すなわちある \(i\) に対して \(A_i=j\) ならば、\(S\) の末尾に \(i\) を \(1\) つ追加する。
- 点 \(j\) がある曲線の右端、すなわちある \(i\) に対して \(B_i=j\) ならば、\(S\) の末尾から \(1\) つ要素を取り出す。この取り出した要素が \(i\) でないならば、交点が存在することを報告してプログラムを終了する。
- 最後までプログラムが終了しなかったならば、交点が存在しないことを報告する。
このアルゴリズムの正当性の証明は省略します。直観的に理解しづらい場合は、上述の条件(*)を「点 \(1\) から点 \(2N\) に向かって左から右に見ていったとき、曲線 \(i\) の左端が来て、その右端が来る前に別の曲線 \(j\) の左端が来たならば、曲線 \(j\) の右端は曲線 \(i\) の右端より先に来なければならない」と考えると、まだ左端しか来ていない曲線を「後入れ先出し」データ構造で管理するというアイデアが多少自然に思えるかもしれません。
実装例 (C++) :
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> v(2 * n);
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
--a, --b;
if (a > b) swap(a, b);
v[a] = {0, i};
v[b] = {1, i};
}
stack<int> st;
for (int i = 0; i < 2 * n; i++) {
auto [t, id] = v[i];
if (!t) {
st.push(id);
} else {
if (st.top() != id) {
cout << "Yes" << endl;
return 0;
}
st.pop();
}
}
cout << "No" << endl;
}
posted:
last update: