2020 ICPC 서울 인터넷 예선

원래는 블로그 글을 좀 자세하고 정확하게 쓰려고 노력하는 편이나, 인터넷 예선은 채점해 보기도 까다롭고 하니 그냥 대충 정리해서 올리려고 한다. 완전 입풀이고, 코드를 한 줄도 안 짜보고 올리는 글이라서, 내용이 부정확할 수도 있다.

(10/20 추가: 현재 C H 빼고 모두 채점이 된다. 해당 문제들에 대해 블로그에 나온 방식으로 구현해서 전부 정답을 받았다.)

A

최종 정렬된 배열을 생각해 보자. 이 배열의 부분배열(연속) 중 원래 입력으로 주어진 배열의 subsequence를 만족하는 최대 길이의 부분배열을 찾으면 된다. 중복이 없으면 그냥 원래 배열에서의 index가 증가하는 최대 길이 부분배열을 찾으면 된다. 아닌게 귀찮은데.. substring 상 서로 다른 원소가 1개, 2개, 3개 이상인 것을 케이스를 나누면 될 것이다. 첫 번째는 쉽다. 두 번째도 뭐 대충하면 된다. 세 번째는 중복이 없는 경우와 크게 다르지 않게 된다.

B

$O(n \times k_1 \times k_2)$ 풀이는, $dp[i][j][k] = $ (길이 $i$ 인 문자열 중 $P_1$ 의 prefix와 현재 최대 매치가 $j$이고 $P_2$ 의 prefix와 현재 최대 매치가 $k$) 라는 점화식을 사용하면 된다. 0과 1을 붙였을 때 다음 상태가 무엇인지는, $P_1, P_2$ 에 KMP를 돌린 후 failure function의 결과물을 전처리하면 알 수 있다. 글에서 말하는 "매치" 어쩌구가 무슨 말인지 잘 모르겠으면 KMP를 이해하면 도움이 될 것이다. 하여튼 이렇게 하면 $10^5 \times 10^4 \times 10^4 = 10^{13}$ 이라서 TLE일 것 같지만, 입력 지문에 써져 있는 어쩌구저쩌구를 대충 예외처리하면 $10^7$ 이라고 어쩌구저쩌구 써져 있다. 어쩌라는 건지..

C

왼쪽 오른쪽 조각을 따로 풀고 최솟값을 취하자. 여기선 편의상 오른쪽 조각만 얘기한다. 문제에서 요구하는 것은 staircase 모양의 다각형에 대해서 일종의 트리 형태의 분할을 찾는 것이라고 할 수 있다. 루트 정점은 오른쪽 아래 꼭짓점을 포함할 것이고, 리프 정점은 계단을 이루는 오목한 꼭짓점에 붙어 있는 최소 크기의 직사각형이다.

답에 대해서 이분 탐색을 해서 결정 문제로 바꾸자. 모든 조각을 크기 $X$ 이상의 직사각형으로 쪼개야 하는데, 어떠한 리프를 현재 떼어낼 수 있을 때 (즉, 어떠한 볼록한 꼭짓점에 대해서 해당 꼭짓점을 포함하는 가장 작은 직사각형을 떼어 낼 수 있을 때). 떼어내지 않아서 볼 수 있는 이득이 없다. 고로 매 순간 가능한 리프를 계속 떼어내는 것을 반복하자. 이것은 priority queue와 std::set (아니면 uf 아니면 링크드 리스트) 정도로 시뮬레이션이 가능하다. $O(n \log n \log X)$

사실 이분탐색 안하고, 그냥 매번 가능한 최소 크기 리프를 떼어내도 될 것 같다. 이렇게 하면 $O(n \log n)$ 이 된다.

1211789 팀은 아주 간단한 $O(n)$ 에 풀었다고 한다. 문제에서 나온 계단을 길이들의 수열 (길이 n+1개) 로 나타낸 뒤 맨 앞, 두번째, 맨 뒤, 뒤에서 두번째, 그리고 인접한거 두개 최댓값들. 이 5개 중에 최솟값을 찍었다고 한다.

D

DP로 LIS를 구하는 것과 유사하게 해결할 수 있다. DP 테이블을

• $A[i] = $ ($i$ 에서 끝나는 수열 중 마지막이 감소했던 수열)
• $B[i] = $ ($i$ 에서 끝나는 수열 중 마지막과 두번째 마지막이 감소했던 수열)
• $C[i] = $ ($i$ 에서 끝나는 수열 중 마지막이 증가했던 수열)
• $D[i] = $ ($i$ 에서 끝나는 수열 중 마지막과 두번째 마지막이 증가했던 수열)

처럼 정의하면 $n^2$ 상태전이는 (귀찮으나) 자명하고 이를 segment tree로 최적화하면 된다.

E

Union-find 자료구조를 사용하면 어떤 턴에서 사이클이 완성되었는지를 효율적으로 알 수 있다.

F

도둑의 최적 전략은 한쪽 방향으로 무작정 도망가는 것이다. 모든 4방향을 시뮬레이션 해본 후 경찰이 못 잡는 경우가 있는지 확인한다. 동치인 풀이는, 평면을 45도 돌린 후, 1/2/3/4 사분면 모두에 경찰이 하나씩 있는지 본다 (이 때 사분면은 x, y축을 포함한다).

G

SCPC 2018 본선 5번의 섭테였던 문제이다. https://arxiv.org/pdf/1705.09346.pdf https://arxiv.org/pdf/1802.09505.pdf

풀이를 간단히 요약하자면, 각 원이 취할 수 있는 가능한 반지름의 개수가 많지 않다. $r_i = a_{i + 1} - a_i$ 라고 하자. 각 점에서 취할 수 있는 반지름의 최소는 0이고, 최대는 $min(r_{i-1}, r_i)$ 이다. $r^2$ 라는 함수 특성상 큰 놈은 크게 몰아주고, 작은 놈은 작게 몰아주는 전략이 전반적으로 성립하기 때문에 이상적으로는 저 둘 중 하나만 골라도 되겠지만, 어떤 경우에는 양 옆에 있는 원이 더 커질 수 없는 상태에서 내가 먹을 공간이 비는 경우가 존재하기도 한다. 양 옆의 원 ($i-1, i+1$) 이 커질 수 없었던 이유가 다 있었을 것이다. 이미 최대를 찍어서일수도 있고, 또 그 옆에 있는 어떤 공간($i-2, i+2$) 이 먹혀서일 수도 있을 것이다. 옆에 있는 공간이 먹혔다고 하면, 그 공간을 먹게끔 한 걸 계속 따라가고... 반복하면, 반지름 최댓값인 어떤 원을 기점으로, 번갈아가면서 반지름을 배정하는 꼴이 된다.

이제, 각각의 원 $i$가 최댓값인 경우를 모두 나열하고, 왼쪽 오른쪽으로 뻗어나가면서 이 때 다른 원 $j$ 의 "유도된 반지름" 을 계산하면 각 원마다 $O(n)$ 개의 가능한 반지름 후보가 생긴다. 이제 문제는 DP 문제가 되고 $O(n^2 \log n)$ 에 해결 가능하다.

후보를 $O(1)$ 으로 줄이는 방법은, 유도된 반지름을 모든 $i$ 에 대해서 볼 필요가 없다는 것이다. 한 $j$에 대해서 봐야 할 후보는 대충 $j-1, j+1$, 그리고 $r_j < r_{j + 1} < r_{j + 2}$ 와 같은 증가/감소 체인이 끝나는 시점 (오른쪽 왼쪽 모두), 이렇게 한 4가지 정도만 보면 된다. 그래서 같은 DP로 $O(n \log n)$ 에 해결 가능하고, 조금 귀찮게 하면 $O(n)$ 도 된다. 사실 내용들이 다 직관적으로 그럴듯 하긴 한데 증명하자면 까다롭다. 논문에서 되게 깔끔하게 증명을 해 놨으니 관심 있으면 읽어보자.

여담으로 생각보다 구현이 까다로워서 꼼꼼하지 않으면 맞왜틀 지옥에 빠질 가능성이 높다. 이 글에도 빼먹은 디테일이 많으니 맹신하지 말자.

H

만약 모든 간선이 -1이라고 하면 이는 그래프에서 Odd cycle을 찾는 문제가 된다. 이분 그래프를 제외한 모든 그래프는 odd cycle이 존재하며 DFS를 통해서 찾을 수 있다.

+1 간선이 추가되었을 때, +1 간선이 잇는 정점들을 한 정점으로 묶고 생각하면 그냥 동일한 문제임을 알 수 있다. 그렇다고 구현할때 +1 간선이 잇는 정점을 정말 묶어줄 필요는 없고, 그냥 위에서 odd cycle을 찾은 루틴을 조금만 변형해서 구현하면 된다.

I

정렬한 후 $(i, 2n+1-i)$ 를 묶어주자.

J

부분합 배열 $S$를 만든 후 $S_i - S_j$의 $k$ 개의 최댓값을 찾는 문제다. 두 가지 풀이가 있다.

첫번째는 쉬운데 좀 느린 풀이. $k$ 번째 값이 뭔지를 알면, 힙이나 셋 등등 적절한 자료구조를 통해서 1~k번째 값을 모두 알 수 있음을 관찰하자. 그래서 $k$ 번째 값을 이분 탐색으로 찾자. $S_i - S_j >= X$ 인 $(i, j)$ 의 개수가 $k$ 이상인지 판단하는 건데 이는 좌표 압축 후 fenwick tree로 $O(n \log n)$ 에 판별할 수 있다. 시간 제한이 빡세서 느린데, 1. 잘 짜고 2. 이런 저런 커팅을 하면 잘 되는 듯 하다 ㅋㅋ 누가 이걸로 맞았다고 함

내가 생각한 $O((n + k) \log n)$ 은 복잡하다. 일단 첫번째 최댓값은 $S_i - min_{j < i}(S_j))$ 중 하나가 될 것이다. 그래서 그 중 하나를 뽑았다면, 뭐 예를 들어 $S_x - S_y$ 를 뽑았다면, 나머지는 $S_i - min_{j < i} (S_j)$ 가 그대로고, $x$ 에 대해서만 두번째 최솟값을 뽑아야 한다. 이 정보를 heap으로 관리하자. heap에 (i, 몇 번째 최솟값을 뽑아야 하는지, 그래서 뽑았을 때 비용) 의 tuple을 저장한 후 $k$ 번 뽑아주면 된다. 힙을 관리하기 위해서는 prefix에 있는 원소 집합 중 $k$ 번째 최솟값을 찾아야 한다. 좌표 압축 후 Persistent segment tree를 구성하면 된다.

K

모든 조건은 격자의 특정 셀을 방문하기 위한 비용으로 해석할 수 있고 고로 최단 경로를 묻는 문제이다. Dijkstra algorithm을 사용하면 된다.

L

길이 $n-2$ 의 수열과 $2$ 의 수열을 merge해서 (각각의 상대 순서를 유지해서) 원하는 수열을 만들 수 있는가를 찾는 문제이다. $dp(i, j)$ = (첫번째 수열의 앞 $i$개, 두번째 수열의 앞 $j$ 개를 merge해서 $i + j$ 길이의 prefix와 match 시킬 수 있는가) 로 정의하면 $O(n)$ 에 문제가 해결된다. DP를 안 써도 풀릴 수도 있겠다.