ABC091 C - 2D Plane 2N Points

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import datetime

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def it(): return tuple(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    red, blue = [], []

    for _ in range(N):
        x, y = il()
        red.append([x, y])
    for _ in range(N):
        x, y = il()
        blue.append([x, y])

    # 予めx座標でソート
    blue.sort()
    red.sort()
    used = [False] * N
    ret = 0
    for i in range(N):
        bx, by = blue[i]
        tmp = -1
        for j in range(N):
            rx, ry = red[j]
            if used[j]:
                # 既に組み合わせの存在する赤い点
                continue
            if rx > bx or ry > by:
                # 青い点と組み合わせることが出来ない
                continue
            if tmp != -1 and red[tmp][1] > red[j][1]:
                # 組み合わせることができる他の赤い点より
                # y座標が小さい場合
                continue
            tmp = j
        if tmp != -1:
            used[tmp] = True
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()

考え方

解説読んで回答したため、
ほぼ解説の通りに条件を付けてペアの個数をカウントしました。
予め各赤と青の座標のリストをソートしておくと実装しやすいと思います。