SCUPC 2022 후기

https://www.acmicpc.net/contest/view/912

 

간략하게 씁니다. 디테일을 안 쓰는 이유는 기억이 안나서...

 

A $7.5N-len$ 이 0 이상인지 이하인지를 가지고 판단했습니다. 더 짧게 짜라면 짤 수 있을듯

B 그냥 하면 됨

C O(N) 풀이가 있다고 합니다. https://www.acmicpc.net/problem/4354 랑 비슷하게 풀면 됨

D 현재 위치와 현재 시간의 차이가 같은 금고를 모두 털 수 있습니다

E 현재 위치와 현재 시간의 차이가 증가하도록 금고를 털 수 있습니다. 이후는 LIS 알고리즘

F 앞쪽 절반만 보면 수가 증가해야해서 중복순열을 쓰면 됩니다

G 이분탐색 + 슬라이딩 윈도우쓰는 재미있는 문제라고 생각함

H (수열의 길이, 수열에 올 수 있는 다음 원소)중 파레토 최적인 것을 따져주면 됩니다. (수열의 길이가 짧고, 수열에 올 수 있는 다음 원소가 큰 경우에 해당 수열은 무시해도 됩니다) 뭔가 풀이 자체는 되게 간단하고 구현도 map 같은걸 쓰면 간단한데 아이디어가 신기합니다 원래 Ai가 1 이상이었는데 그냥 제가 이 풀이 찾아서 0으로 바꿈

I 정해는 뭔가 케웍 엄청 하던데 백트래킹을 잘 짜면 됩니다. 남은 수들을 1324 식으로 배치하는걸 기본적인 배치로 잡는데, 중간에 불가능한 부분을 깔끔하게 백트래킹으로 처리할 수 있어서 제 코드는 60줄 정도

 

J

A -> B로 가는 법은 다음 중 하나입니다

- A에서 B로 그냥 순간이동을 안 쓰고 감 (이건 쉬우므로 넘어갑니다)

- A에서 아무 명신대사를 간 이후, 어떤 거리 $x$를 정해서, B로부터 거리 $x$ 미만인 명신대사가 나올 때까지 순간이동을 쓰고, 그 이후에 B로 감

이게 사실 임의의 포탈에서 순간이동을 한 번 쓴 이후 B로 가는 기댓값이 곧 $x$라서, 기댓값이 $x$보다 큰지 작은지를 판단하면 이분탐색같은걸 써서 답을 찾아줄 수 있습니다.

$x$가 주어지면 "정점 $v$에 대해 거리가 $x$ 이내인 정점들까지의 개수와 거리 합" 같은 문제를 풀어야 하는데 저는 이게 온라인으로는 잘 안 풀리고 오프라인으로는 풀렸습니다. 센트로이드를 돌리든 분할정복을 돌리든 뭘 하면 문제가 풀립니다.

그래서 각 정점 $v$에 대해서 이분탐색을 병렬적으로 돌리는 Parallel Binary Search를 끼얹으면 문제가 풀립니다.

 

다른 신기한 자료구조를 사용해서 convex hull을 관리하면서 푸는 방법도 있던데 저는 잘 모릅니다... 애초에 문제가 엄청나게 구현-intensive해서 본대회때 푸는 사람이 나올지도 몰랐음

 

K

결국 문제 자체는 $\sigma^{-1}$라는 순열이 숨겨져 있고, $\pi_i$ 들을 주면 $\sigma^{-1}(\pi_i)$의 LIS를 반환합니다.

쉬운 버전은 https://www.acmicpc.net/problem/3503 가 있고, 이거 풀이를 먼저 설명하겠습니다.

$a_1, a_2, \cdots, a_N$ 에서 $a_1$이 LIS에 항상 포함되는 원소라는 것은, 이 수열에서 $a_1$을 제외하면 LIS의 길이가 $1$ 짧아진다는 것을 의미합니다.

즉, $a_2, \cdots, a_N$ 사이에다가 아무데나 $a_1$을 끼워넣은 $a_2, \cdots, a_j, a_1, a_{j+1}, \cdots, a_N$을 쿼리해봤을 때

• LIS의 길이가 $1$ 짧아지면 $a_1, a_2, \cdots, a_N$ 에서 $a_1$이 항상 LIS에 포함된다는 것을 의미합니다.
• LIS의 길이가 $1$ 늘어나면 $a_2, \cdots, a_j, a_1, a_{j+1}, \cdots, a_N$ 에서 $a_1$이 항상 LIS에 포함된다는 것을 의미합니다.

이런 방식으로 $a_1$이 LIS에 포함되는것을 확정시키거나, LIS의 길이를 $1$ 늘릴 수 있습니다. 디테일들이 좀 더 있긴 합니다. 이러면 $N^2$ 미만의 쿼리로 문제를 풀 수 있습니다.

 

이제 더 줄여봅시다. 임의의 두 원소를 비교할 수 있으면 binary insertion sort를 사용할 수 있습니다. $100$개의 수를 이용해서 binary insertion sort를 하면 573번의 비교가 필요하기 때문에, 비교를 제외한 여유 연산 $4N+\log N$번 정도가 있습니다.

 

===

 

새로운 관찰을 합니다.

• $a_1, a_2, \cdots, a_N$ 에서 $a_1$이 항상 LIS에 포함되는 원소라고 합시다. $a_i, a_1, a_2, \cdots, a_{i-1}, a_{i+1}, \cdots, a_N$의 LIS 길이가 $1$ 증가하는 것과 $a_i < a_1$은 동치입니다.

그래서 $a_1, a_2, \cdots, a_N$을 찾고 $a_1$이 항상 LIS에 포함된다는 것을 알면, $a_1$과 임의의 수를 비교할 수 있습니다. 만약 $a_1$이 적당히 크다면 $a_1$을 기준으로 수들을 파티션 할 수 있을 것입니다. (pivot으로 사용할 수 있습니다) 이제 적당히 큰 $a_1$을 찾아봅시다.

 

$a_{(i+0) \mod N}, a_{(i+1) \mod N}, \cdots, a_{(i+N-1) \mod N}$의 LIS를 $L_i$라고 합시다. $L_i$가 $L_{i+1}$보다 크다면 $a_i$를 pivot으로 사용할 수 있습니다. 이제 $L_1, L_2, \cdots, L_N$을 모두 찾은 이후 $L_i$가 $L_{i+1}$보다 큰 시점을 찾으면 $N$번의 쿼리로 pivot으로 사용할 수 있는 수들을 몇 개 얻었습니다.

 

이제 다음과 같은 명제를 살펴볼 수 있습니다. 증명은 생략합니다.

• 우리가 찾은 pivot 중, 크기가 가장 큰 pivot의 기댓값 $a_p$는 $2 \sqrt N + o(\sqrt N)$이다.

처음에 한 관찰과 같이 이용하면, $N+a_p$번의 여유연산으로 $a_p$개의 원소를 모아서 정렬할 수 있습니다. $a_p \ge 2 \sqrt N$이 될 때까지 위 과정을 반복해주면, $1-10^{-18}$ 이상의 확률로 $3$번만 반복해서 원소를 찾을 수 있습니다. 이러면 $300$번 정도의 여유연산으로 첫 $20$개의 원소를 정렬할 수 있습니다.

 

===

이제 임의의 두 수를 비교할 수 있는 방법을 찾아봅시다. (두 번째 명제의 증명은 또 생략합니다)

• $L = 1, 2, \cdots, a_p-1$ 의 LIS의 길이는 $a_p-1$입니다. 나머지 $R^s: a_p + 1, \cdots, N$을 shuffle한 수열 의 평균 LIS의 길이는 $2 \sqrt{ N - a_p} + o (\sqrt {N - a_p})$입니다.

 

$R^s, a_p, L$의 LIS의 길이는 $R^s$의 LIS의 길이와 $a_p-1$의 최댓값입니다. 만약 이 값이 $a_p-1$이 나온다면, $R^s, L, a_p$ 수열의 LIS는 $1, 2, \cdots, a_p$로 유일하다는 것을 알 수 있습니다. 평균 $2$번 이하로 위 과정을 반복해서 적당한 $R^s$를 찾을 수 있습니다.

 

이제 $R^s$에서 두 원소 $x, y$를 꺼내와서 $(R^s \setminus \{x, y\}), L, a_p, x, y$ 순으로 썼을 때 LIS가 $2$ 증가하면 $x < y$, $1$ 증가하면 $x > y$이므로 두 원소를 비교할 수 있고 이제 binary insertion search를 돌리면 됩니다.

 

===

 

이 대회에서 J, K를 출제 했고 (검수가 없어서 슬펐고) 좋은 문제 두 개를 다 써버려서 이제 2023 SCUPC에는 무슨 문제를 내야 할지 모르겠습니다. 문제나 고민하고 세팅이나 하러 가겠습니다.