SCPC 2024 간략한 풀이

2, 4, 5번 문제의 아이디어를 구상했다.

시간 여행

각 $i$ 에 대해 $j \le i, A_i - K \le A_j \le A_i$ 를 만족하는 최소 $j$ 를 찾아 그 합을 출력하는 문제이다. $j \le i$ 조건은 함정이다. 어차피 $i$ 가 조건을 만족하기 때문에 무조건 저 조건은 성립한다. 그러면 $A_j$ 값이 특정 구간에 있는 최소 $j$ 를 찾는 문제가 되고, 이는 sliding window minimum 문제이다. $O(N + maxA)$ 나 $O(N \log N)$ 에 해결할 수 있다.

공장

단순하게는 끝점 작은 순으로 구간을 처리하면서 기존에 넣은 구간과 겹치지 않는 구간을 추가해 주면 된다. 쿼리가 들어올 때, 쿼리로 추가된 구간을 끝점 작은 순으로 정렬하자. Merge sort를 하듯이, 두 정렬된 구간 집합을 보면서 끝점이 작은 것을 뽑아주고 추가하려고 시도하면 된다. 이것을 쿼리로 주어진 구간 개수에 비례하게 하려면, 이미 입력에서 주어진 구간을 빠르게 jump해야 한다. 이는 sparse table을 사용하면 된다.

점 잇기

수열의 길이를 $n$ 이라고 하자. 원 상에서 연속한 같은 문자를 숫자 하나로 치환하자. 예를 들어 AABABBAA -> {4, 1, 1, 2} 와 같이 변환한다. 직선이 아니라 원임에 주의하자. 이 수열의 길이를 $2m$ 이라 하자 (무조건 짝수). 그 경우:

• 수열에 1만 등장하면 답이 $\min(2, m -1)$
• 2가 하나라도 등장하면 답이 $0$ 아니면 $1$ 이다. 2를 지우고, 그 양옆에 생기는 2를 반복하면서 지우는 식이다. 최종적으로 $[1, 2]$ 아니면 $[2, 2]$ 꼴의 수열을 얻게 되는데 첫 결과가 나오면 답은 $1$ 이고 두 번째 결과가 나오면 답은 $0$ 이다. 만약 수열 상에 $1$ 로 이루어진 길이 $n/2$ 의 연속 구간이 있으면 첫 번째 결과를 피할 수 없게 된다.

접두사와 접미사

kmp (z-algo), suffix array 등으로 $lcp(B, C[i..])$를 다 계산해두자. 또한. $PrefixSuffix(A_i, C)$ 를 kmp로 계산해두자.

$A_i$ 가 고정되었을 때, $B$ 의 문자를 하나씩 붙이다 보면 실패가 생기고 그 경우 $A_i$ 는 $C$ 의 Failure function을 타고 $PrefixSuffix(A_i, C)$ 에서부터 올라가게 된다. (그게 아니더라도 그냥 lcp 매치를 최대화하고 싶어서 올라갈 수도 있는데, 그건 failure function 부모 보면서 맥시멈 갱신해줌)

붙이는 $B_j$의 길이에 따라서 A가 있게 될 위치가 달라지고, 이 위치가 답을 결정한다. Failure function으로 트리를 만들면, 부모를 따라 올라가면서 최댓값이 갱신되는 위치마다 특정 값을 합하는 식으로 답을 쓸 수 있다.

정리해보면 root - node path 에 대한 monotone stack을 얻으면 된다는 결론에 도달한다. 단순 DFS를 하면 스택을 얻을 수 있는 데, pop back이 amortize가 안 되기 때문에 CEOI 2009 harbingers처럼 이분 탐색으로 pop-back을 구현해 준다.

시간 복잡도는 pop-back에 사용되는 이분 탐색 때문에 $O(n \log n)$ 이다. small-to-large 로 $O(n \log^2 n)$ 에 할 수도 있으며 두 풀이 모두 매우 여유롭게 통과한다. 선형 시간 풀이도 존재한다고 들었다.

동적 사이클 계산 쿼리

사이클 집합이 같을 조건은

• 두 간선이 모두 절선
• 두 간선이 모두 절선이 아닌데, 두 간선을 같이 제거하면 컴포넌트 개수 증가

이다. Offline Dynamic Connectivity를 사용하여 이 조건을 계산하면 아마 345점을 얻을 수 있다. (굉장히 쉽게 고득점을 얻을 수 있는 방법이었지만 실제 얻은 참가자는 없었다.)

만점 풀이는 세그트리를 처음에 다 채워넣고 시작하는게 아니고, 각 간선 추가 쿼리에 대해서 “사용함이 확실한 다음 지점”까지만 추가해 놓고 그 이후 행보는 필요할때 결정하는 식이다. 해당 간선을 사용함이 확실한 지점은, 그 인덱스가 등장하는 다음 삭제/질의 쿼리까지이니 이분 탐색으로 결정 할 수 있다. 추가하는 건 Offline Dynamic Connectivity에서 현재 순회하고 있는 세그트리에 구간 갱신을 해 주면 된다. 순회와 갱신을 같이 하는 것이 매우 비직관적이지만, 잘 생각해보면 순회 도중에 구간 갱신을 해도 상관이 없다.

시간 복잡도는 $O(n \log^2 n)$ 인데 $O(n \log n)$ 으로도 구현할 수 있다. Online dynamic connectivity를 사용한 $O(n \log^2 n)$ 은 굉장히 느리기 때문에 시간 제한을 통과하지 못할 것이다.