hiro1729 競プロ

競プロの解説などを書きます。

ABC338-E 解説

AtCoder ABC ABC338 ABC-E 水diff stack FenwickTree

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"