Algospot.com 10주년 모의고사

출제진으로 참여했던 알고스팟 10주년 기념 대회가 무사히 끝났다. 출제진의 수가 적어서 많은 문제를 냈는데, 출제한 문제 5개(D, F, G, H, L)에 대해 간략한 출제 배경과 풀이를 써 보았다.

Problem D. Dynamic Input Tool

subsequence가 아닌 substring인 버전이 opencup에 있고, 그 문제가 있는 셋을 돈 후에 출제하였다. 5개 중 마지막으로 낸 문제인데, 난이도는 가장 낮다. 

1. 전처리 : 각 위치, 각 알파벳에 대해 그 위치 이후에 그 알파벳이 처음으로 오는 위치를 저장해 놓는다. 

2. 앞에서부터 본다. 현재 입력해야 하는 위치가 i이고, subsequence가 pivot까지 왔을 때, pivot 이후에 i가 오는 처음 위치를 pivot에 넣고, i를 1 증가시킨다. 만약 pivot이 i 이상이 되면 pivot을 처음으로 돌린다. 이렇게 그리디하게 풀면 올바른 답이 구해짐을 쉽게 알 수 있다.

Problem F. Fan of Computational Geometry

디스크립션이 잘못 쓰여 있는 문제를 매우 많이 틀렸던 기억이 떠올라서 이를 바탕으로 만든 문제이다(저 문제는 선분을 직선이라고 해석해야 맞을 수 있다). 좋은 문제를 만들려고 했지만 결국 원본처럼 망한 비운의 문제이다.

먼저, x축과 y축에 매우 긴 선분을 하나 놓고, 나머지 선분을 1사분면 또는 3사분면에 놓는다고 하면 사이클은 1사분면 내에서 생기거나 3사분면 내에서 생긴다. 

위 그림에서 AB, CD를 고정하고, 나머지 선분들은 한쪽 끝점은 그대로 놔두고 다른쪽을 줄이는 방법으로 1부터 1000까지 모든 답을 만들 수 있다. (실제로는 2000까지도 가능하다)

위 풀이는 테스트 케이스가 많이 주어져도 관계없는 풀이이다. 하나의 테스트 케이스만 주어지는 문제이기 때문에 랜덤으로도 잘 풀리는데, 그래프 만들기 / 사이클 세기 함수를 만든 후에 랜덤을 잘 돌리면 AC를 받는 것이 가능하다.

Problem G. Game of Sorting

이번 대회에 낸 문제 중에서는 가장 마음에 드는 문제이다. 원래는 쿼리 문제가 아니었는데 출제진의 킹갓께서 쿼리도 가능하다고 하셔서 수정하였다.

수열이 b번째 항부터 e번째 항까지 있을 때, 이를 A[b,e]라 하자. A[b, e]가 초기 상태일 때 Alice가 이기면 Win[b, e]  = 1, Bob이 이기면 Win[b, e] = 0이라 하자.

만약 A[b, e]가 비증가 또는 비감소이면(monotone이면) Win[b, e] = 0

그렇지 않으면 Win[b,e] = (!Win[b,e-1]) | (!Win[b+1, e])이다.

몇 가지 경우를 제외하면 Win[b,e] = Win[b+1, e-1]가 성립하는데, 성립하는 경우에 대해서 b+e가 결정되면 답이 결정됨을 알 수 있다.

어떤 수열 A에서 길이 L인 연속된 부분 수열이 존재하여 monotone이고, 또한 길이 (L+1)인 monotone인 연속 부분 수열이 존재하지 않을 때, A를 L-monotone이라 하자.

1. A[b, e]가 (e-b+1) - monotone인 경우 -> 전체가 monotone이므로 Win[b, e] = 0

2. A[b, e]가 (e-b) - monotone인 경우 -> 양 끝 중 하나를 제거하면 monotone이다. Win[b, e] = 1

3. A[b, e]가 (e-b-1) - monotone인 경우

   3-a. 오른쪽 끝 2개 또는 왼쪽 끝 2개를 제거했을 때 monotone인 경우 -> 일반성을 잃지 않고  A[b, e-2]가 monotone이라 하자. 이 때 Win[b, e] = !Win[b+1, e] = Win[b+2, e] = !Win[b+3, e] = .... 임을 알 수 있다. A[L(e), e]가 monotone인 최소의 e를 L(e)라 할 때, L(e)의 값을 알면 Win[b, e]를 구할 수 있다.

 3-b.  가운데 (e-b-1)개가 monotone인 경우 ->Win[b,e] = 0임을 쉽게 알 수 있다.

4. 위의 3가지 경우가 아닌 경우 -> Win[b,e] = (!Win[b,e-1]) | (!Win[b+1, e]) = (Win[b, e-2] & Win[b+1, e-1]) | (Win[b+1, e-1] & Win[b+2, e])인데 Win[b+1, e-1] = 0이면 Win[b, e] = 0이고, Win[b+1, e-1] = 1일 때 Win[b, e] = 0이려면 Win[b, e-2] = Win[b+2, e] = 0이어야 하는데 A[b, e-2], A[b+1, e-1], A[b+2, e]가 모두 monotone이 아니므로 이것이 불가능함을 알 수 있다. 따라서, Win[b, e] = Win[b+1, e-1]이다. 

Problem H. Hole in a Circle

기하 문제를 내려고 했지만 어느새 자료구조 문제가 되어 있었다. 사실 기하였으면 대회 밸런스 측면에서 매우 안 좋았을 듯.. 처음에 의도한 풀이보다 더 빠른 풀이가 존재했다.

최단 거리가 가장 먼 두 집은 원의 중심과 두 집이 이루는 각이 가장 큰 두 집이고, 거리는 그 각에 대한 함수이므로 가능한 360000 / 2 = 180000가지 경우에 대해 거리를 미리 전처리하여 구해 놓는다.

이제 각 쿼리에 대해 중심각이 가장 큰 두 집을 구하면 된다.

만약 집을 짓는 쿼리만 있다면, set으로 집들의 위치를 관리하면서  새 집이 지어질 때 그 반대편과 가장 인접한 집의 위치를 구하면 답을 갱신해줄 수 있다. 이 때 시간복잡도는 O(Q log N)이다.

어떤 집이 b번째 쿼리에 생겨서 e번째 쿼리에 없어졌다고 하자. 이를 세그먼트 트리의 O(log N)개 노드에 저장하고, 세그먼트 트리를 전위순회하면서 처리하면 삽입 쿼리만 하면서 답을 계산할 수 있다. 이 때 삽입이 O(Q log N)번 일어나므로 전체 시간복잡도는 O(Q log^2 n)이 된다. 

위 풀이가 intended solution이지만, online으로 O(Q log N)에 푸는 방법이 존재한다.

set에 집의 위치를 저장하고, priority queue에는 답이 될 수 있는 두 집의 번호를 저장한다. (각이 크면 우선순위가 높은 priority queue이다)

초기 상태 : 각 집 i에 대해 i에서 가장 먼 집을 far(i)라 하면 priority queue에 (i, far(i))를 삽입한다.

insert : 새로 지은 집과 그 집에서 가장 먼 집 순서쌍을 priority queue에 삽입한다.

delete : delete한 위치에서 시계방향으로 가장 가까운 집을 h1, 반시계방향으로 가장 가까운 집을 h2, delete한 위치의 반대 지점에서 시계방향으로 가장 가까운 집을 h3, 반시계방향으로 가장 가까운 집을 h4라 할 때 h1, h2, h3, h4에 대해 (h_i, far(h_i))를 priority queue에 삽입한다.

이 때 답은 priority queue에서 top에 있는 두 집이 현재 모두 available한 상황일 때까지 pop한 후 top에 있는 두 집 사이의 최단거리가 된다. 시간복잡도는 O(Q log N).

Problem L. LIS++

LIS에 관련된 어떤 문제를 풀다가 LIS 관련 문제를 아무거나 내자 해서 낸 문제이다. 난이도는 적당한 것 같다.

수열 {a_n}이 있을 때 LIS를 다음과 같은 방법으로 구할 수 있다.

M[j] : 길이 j인 increasing subsequence의 마지막 수로 가능한 최소값

으로 배열 M을 정의하자. 수열의 맨 끝에 수 a가 추가되었을 때의 배열을 M'이라 하자. M[k] < a인 최대 k에 대해 M'[k+1] = a을 만족하고, 그 외의 경우 M'[j] = M[j]가 성립한다. 따라서, 수 하나를 뒤에 추가할 때마다 lower_bound를 통해 M을 갱신하면서 O(N log N)에 LIS를 구할 수 있다.

이를 응용하여 다음과 같이 DP 배열을 만들자.

D[i][mask] : i번째 숫자까지 보았을 때,  배열 M의 bitmask 표현이 mask가 되도록 subsequence를 고르는 경우의 수

(예를 들어, T = 50234일 때 D[2][1] = 2, D[3][32] = 1, D[3][33] = 0, ..)

비트연산을 이용하면 O(N * 2^10)에 DP 배열을 채워 문제를 해결할 수 있다. 2차원 배열을 직접 잡으면 메모리가 부족하므로 토글링을 통해 문제를 해결하여야 한다.

난이도 : 상

추천 문제 : C, G, H / 도전 문제 : B / 알고리즘 연습 문제 : K / 안 좋은 문제 : F