오전 셋

대전 Regional 2017중 몇개를 돌았다.

ICPC같이 풀이를 얻기 쉬운 셋들은 귀찮으니까 이름 외에는 아무것도 안적으련다.

Happy Number

Game Map

Philosopher’s Walk

Connect3

Rectlinear Regions

Untangling Chain

Vacation Plans

오후 셋

어제 있었던 KOI 2018을 돌렸다. 본선에선 서버가 폭렬하게 터진 듯 하지만…

  1. Arrows

  2. Xcorr

  3. Matrix

triplet 들을 적당히 골라서, 순서관계가 명확하게 생기도록 할 수 있는 최대 개수를 구하는 문제다. 혹은 2D에서 LIS를 구하는 것.

두가지 풀이가 있다.

x축으로 정렬하고 분할 정복을 하는 것. [s, e] 에서 분할 정복을 한다고 하면, [s, e] 에 속하는 인덱스의 각각의 최적값을 구한 것이다. 즉, [s, e] 에서 봐야 하는 $latex부 O( [s, e] ^2) $ 개 쌍들을 전부 처리해주었다는 것이다.

그러면, [s, e] 을 분할정복할 때 [s, m] 을 정복하고, [m+1, e] 을 정복하고 나면, [s, m] 이 [m+1, e] 구간에게 보이는 것만 처리해주면 된다. 그러니 [s, m] 구간에 속한 점들을 그냥 다 세그트리같은곳에 넣고, [m+1, e] 에 속한 점들이 세그트리를 돌면서 보면 된다.

이러면 O(Nlog^2N) 에 된다

다른 하나는 같은 D[x]값 (LIS길이)를 가지는 점들에 대해서, 계단 모양을 만들어서 관리해 주는 것이다. 계단의 안쪽은 항상 비어 있어야 하고, 이는 set같은걸 쓰면 빠르게 관리할 수 있다. 만약 D[x]값이 t인 점들 중 하나가 내 안쪽에 있다면, t-1인 점들 중 내 안쪽에 있는 것이 있으므로, 파라메트릭으로 O(Nlog^2N) 에 가능하다.

  1. Family

각 정점이 포함하는 리프들의 집합을 각각 A[v], B[v]라고 하면, 모두 모아서 봤을 때 임의의 두 집합을 고르면 disjoint하거나 포함하는 관계를 가지면 된다.

원래 트리에서 집합들을 나타내 봤을 때 그 집합들은 위의 조건을 만족하며, 문제에서 주어진 연산을 하면 한 집합이 없어지게 된다. 따라서 A와 B에서 얻을 수 있는 집합을 모두 모으면 원래 트리의 집합들의 집합에 속하게 되고, 따라서 문제 조건을 만족하려면 위의 조건을 만족해야 한다.

또한, 위의 조건을 만족하는 두 트리는 하나의 원본으로 reconstruct할 수 있다.

작은 집합들부터 보면서, 리프들을 union find해가면서 보면 된다. 귀찮아서 이하생략. 총 O(NlogN) , 정렬을 counting으로 하면 O(N) 으로 된다.