장애물 경기

• x방향으로의 이동거리는 일정하니, y방향으로의 이동거리만 계산해주면 된다.
• 처음 출발점의 y좌표를 y0 이라고 하자. y0까지의 이동거리 d[y0] = 0이고, 임의의 y' 까지의 이동거리 d[y']은 d[y0] + abs(y'-y0) 이 된다.
• 이제 [yl,yh] 범위의 장애물을 하나 거친다고 하자 (yl<y0<yh). 이 이후에는 yl<y'<yh 인 y'까지 이동하려면 yl까지 갔다가 돌아가거나 yh까지 갔다가 이동해야 하므로, 이동거리 d[y']은 min(d[yl]+abs(y'-yl), d[yh]+abs(y'-yh)) 이 된다. yl보다 작거나 yh보다 큰 y'까지 이동하는 거리도 같은 식으로 나타낼수 있다. 결국 d[y0]는 더이상 필요없고, d[yl], d[yh] 만 있으면 모든 점까지의 거리를 계산할수 있다.
• 이런식으로 장애물을 지날때마다 기준점들을 업데이트 해주면, 장애물을 지난 뒤에 특정 위치까지 이동하는 거리를 min(d[y_i]+abs(y'-y_i)) 식으로 계산 가능하다. 기준점을 업데이트 해주는 것은, 장애물 범위 안에 있는 기준점들을 지워주고, 장애물에 양끝점을 기준점에 추가해주면 된다. 장애물 범위 안에 기준점이 없으면 업데이트 할 필요도 없다.
• 먼저 장애물들을 정렬하는 과정에서 O(nlogn)이 필요하다. 이후에 장애물 한개를 처리할때마다 기준점을 2개씩 추가하게 된다. 전체 과정에서 추가되는 기준점이 총 2n개이니까, 삭제되는 기준점도 최대 2n개이고, 거리계산도 최대 4n번 하게 된다. 사실 이것만 필요하다면 딕셔너리를 써서 각각의 연산을 O(1)로, 총 O(n)에 처리하는것도 가능한데, 문제는 삭제해야 하는 기준점을 찾는 부분이 추가로 필요하다. 현재 기준점들 중에서 [yl, yh] 범위에 있는 점을 찾아야 하는데, 이것을 효율적으로 하기 위해서는 딕셔너리가 아닌, 이진탐색트리를 사용해서 O(logn)에 처리해야 한다. 이진탐색트리를 쓸경우, 추가와 삭제도 모두 O(logn)이 되므로 총 시간복잡도가 O(nlogn)이 된다.
• 이진탐색트리를 쓸때 cpp라면 std::map을 쓰면 간단하겠지만, python에서는 기본 제공 이진탐색트리가 없기 때문에 여기에서는 Order Statistic Tree를 사용했다. 이렇게 처리할 경우, 각 연산의 시간복잡도는 원소에 갯수에 따라 달라지는 O(logn)이 아니라, 원소의 최댓값에 따라 달라지는 O(logM)이 된다. 추가하기, 범위내 원소 찾기, 찾은원소 삭제하기가 모두 O(logM)이 되어서, 실제 총 시간복잡도는 O(nlogM)이 된다.
  • 좌표압축을 쓰면 O(logn)으로 줄일수 있긴 하지만, M이 최대 2,000,000에 불과한 이 문제에서는 그게 오히려 비효율적이다.

"""Solution code for "BOJ 13303. 장애물 경기".

- Problem link: https://www.acmicpc.net/problem/13303
- Solution link: http://www.teferi.net/ps/problems/boj/13303

Tags: [BBST]
"""

import sys
from teflib import fenwicktree

INF = float('inf')


def get_nums_between(ost, beg, end):
    k = ost.count_less_than(beg)
    ret = []
    for i in range(k + 1, ost.size() + 1):
        nums = ost.kth(i)
        if nums >= end:
            break
        ret.append(nums)
    return ret


def main():
    N = int(sys.stdin.readline())
    y, x = [int(x) for x in sys.stdin.readline().split()]
    obstacles = [
        [int(x) for x in sys.stdin.readline().split()] for _ in range(N)
    ]

    max_y = max(y, max(y_h for x, y_l, y_h in obstacles))
    ost = fenwicktree.OrderStatisticTree(max_y)
    ost.add(y)
    dist_by_pos = {y: 0}
    for _, y_l, y_h in sorted(obstacles):
        blocked_positions = get_nums_between(ost, y_l, y_h + 1)
        if not blocked_positions:
            continue
        dist_l = dist_h = INF
        for pos in blocked_positions:
            ost.add(pos, -1)
            dist = dist_by_pos.pop(pos)
            dist_l = min(dist_l, dist + pos - y_l)
            dist_h = min(dist_h, dist + y_h - pos)
        ost.add(y_l)
        ost.add(y_h)
        dist_by_pos[y_l] = dist_l
        dist_by_pos[y_h] = dist_h

    min_dist = min(dist_by_pos.values())
    answer = sorted(p for p, d in dist_by_pos.items() if d == min_dist)
    print(min_dist + x)
    print(len(answer), *answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.OrderStatisticTree