E - Chords
円周上に $2N$ 点が等間隔に、$1$ 〜 $2N$ の順に番号づけられて並んでいます。$A_i$ と $B_i$ を結ぶ弦で、交わるものはあるかどうか判定してください。
解法では、$A_i < B_i$ になるようにswapした後の説明をします。
解法1 - stackを使う解法
$0 \le i < 2N$ の順番に以下の操作を繰り返します。
- $A_k = i$ となる $0 \le k < N$ が存在するならstackに $k$ をpushする
- $B_k = i$ となる $0 \le k < N$ が存在するならstackからpopしてその値を $l$ とおく
- $k=l$ なら $A_i$ と $B_i$ の間で弦は交わっていない
- $k \ne l$ なら $A_i$ と $B_i$ で挟まれる部分の内部と外部に跨る弦があるので、交わっている弦がある なので
Yesを出力してexitする
全て終わったら、Noを出力します。$O(N)$ です。
from collections import deque N = int(input()) P = [0] * (2 * N) for i in range(N): A, B = map(int, input().split()) A -= 1 B -= 1 if A > B: A, B = B, A P[A] = i P[B] = N + i st = deque([]) for i in P: if i < N: st.append(i) else: if st.pop() != i - N: print("Yes") exit() print("No")
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> P(2 * N); for (int i = 0; i < N; i++) { int A, B; cin >> A >> B; A--; B--; if (A > B) { swap(A, B); } P[A] = i; P[B] = N + i; } stack<int> s; for (int i: P) { if (i < N) { s.push(i); } else { if (s.top() != i - N) { cout << "Yes\n"; return 0; } s.pop(); } } cout << "No\n"; }
import strutils, sequtils let N = stdin.readLine.parseInt var P = newSeq[int](2 * N) for i in 0..<N: let a_b = stdin.readLine.split().map(parseInt) var A = a_b[0] - 1 B = a_b[1] - 1 if A > B: swap(A, B) P[A] = i P[B] = N + i var st = newSeq[int]() for i in P: if i < N: st.add(i) else: if st.pop() != i - N: echo "Yes" quit() echo "No"
解法2 - Fenwick Treeを使う解法
はじめに $(A_i, B_i)$ の組でsortしておきます。
$A_i < A_j$ のときに弦 $i$ と $j$ が交わっていないかどうかは、$A_i<A_j<B_i<B_j$ かどうかで判定できます。$i$ に対してこれを満たす個数は、$A_j<A_i$ を満たす $j$ が存在しなければ $A_i<A_j<B_i$ を満たす $j$ の個数から $A_i<B_j<B_i$ を満たす $j$ の個数を引くことで求めることができます。これは、Fenwick Treeで $A_i, B_i$ の区間和を効率的に求めたり各操作の終わりに $A_i, B_i$ で $1$ を引いたりすることができるので $O(N \log(N))$ です。
from atcoder.fenwicktree import FenwickTree N = int(input()) P = [[0, 0] for _ in range(N)] fwA = FenwickTree(2 * N) fwB = FenwickTree(2 * N) for i in range(N): P[i] = list(map(int, input().split())) P[i][0] -= 1 P[i][1] -= 1 if P[i][0] > P[i][1]: P[i][0], P[i][1] = P[i][1], P[i][0] fwA.add(P[i][0], 1) fwB.add(P[i][1], 1) P.sort() for A, B in P: if fwB.sum(A + 1, B) < fwA.sum(A + 1, B): print("Yes") exit() fwA.add(A, -1) fwB.add(B, -1) print("No")
#include <bits/stdc++.h> #include <atcoder/fenwicktree> using namespace std; using namespace atcoder; int main() { int N; cin >> N; vector<pair<int, int>> P(N); fenwick_tree<int> fwA(2 * N), fwB(2 * N); for (int i = 0; i < N; i++) { cin >> P[i].first >> P[i].second; P[i].first--; P[i].second--; if (P[i].first > P[i].second) { swap(P[i].first, P[i].second); } fwA.add(P[i].first, 1); fwB.add(P[i].second, 1); } for (auto [A, B]: P) { if (fwB.sum(A + 1, B) < fwA.sum(A + 1, B)) { cout << "Yes\n"; return 0; } fwA.add(A, -1); fwB.add(B, -1); } cout << "No\n"; }
import strutils, sequtils, algorithm type BIT = object n: int a: seq[int] proc initBIT(n: int): BIT = return BIT(n: n, a: newSeq[int](n)) proc add(bit: var BIT, p: int, x: int) = var t = p + 1 while t <= bit.n: bit.a[t - 1] += x t += t and -t proc sum0(bit: var BIT, r: int): int = var s = 0 x = r while x > 0: s += bit.a[x - 1] x -= x and -x return s proc sum(bit: var BIT, l, r: int): int = return bit.sum0(r) - bit.sum0(l) let N = stdin.readLine.parseInt var P = newSeq[tuple[f: int, s: int]](N) fwA = initBIT(2 * N) fwB = initBIT(2 * N) for i in 0..<N: let a_b = stdin.readLine.split().map(parseInt) P[i].f = a_b[0] - 1 P[i].s = a_b[1] - 1 if P[i].f > P[i].s: swap(P[i].f, P[i].s) fwA.add(P[i].f, 1) fwB.add(P[i].s, 1) sort(P) for (A, B) in P: if fwB.sum(A + 1, B) < fwA.sum(A + 1, B): echo "Yes" quit() fwA.add(A, -1) fwB.add(B, -1) echo "No"
