ACM-ICPC Seoul Preliminary 2018

Scoreboard

지끈..

뭐라 뭐라 더 쓰고 싶으나, 내 블로그가 불편한 이야기를 쓰기에 적합한 장소는 아니라고 생각이 든다.

Problems / Solution Sketch

이번에는 문제 난이도가 비슷한 문제들이 많아서, 사람들이 느끼는 난이도에 이견이 매우 클 수 있다고 생각했다. 마음 같으면 스코어보드 읽고 많이 푼 순서대로 정렬하고 싶으나, 스코어보드가 공개되지 않은 상황이라 그냥 블로그 주인장 마음대로 정렬한다.

I. Registration

B. Farm

양의 수 $i$를 1부터 $N-1$ 사이의 정수로 고정하면, 염소의 수는 $N - i$ 마리이다. 그러면 그들이 먹는 음식의 양도 계산할 수 있다. 음식의 양을 $w$ 로 가지는 양의 수의 개수를 세어 주고, 유일하면 그 수를 출력하면 된다. 시간 복잡도는 $O(N)$ 이다. $O(1)$도 되지만 귀찮으니 생략.

L. Three Robots

각각의 정점에서 모이는 데 걸리는 시간은 max(로봇 1에서의 최단 거리, 로봇 2에서의 최단 거리, 로봇 3에서의 최단 거리) 이다. 고로 세 로봇의 위치를 기준으로 한 최단 경로를 계산하면 알 수 있다. 이는 Dijkstra's Algorithm으로 해결할 수 있다. 시간 복잡도는 $O(M\log M)$. $O(N^2)$도 되

지 않았을까 싶다.

H. Path Embedding

주어진 $N-1$개의 정점 쌍에 대해서 거리의 최댓값을 출력하면 된다. 거리가 4 이상인 경우에는 99를 찍으면 되니, 사실상 거리가 3 이하라고 가정하면 된다. 정의를 따라 단순히 각 쌍에 대해서 DFS를 하면 $O(N^2)$ 알고리즘이 된다. 고로 효율적인 알고리즘을 찾아야 하는 문제이다.

이 문제는 rooted tree의 LCA에 대한 기본적인 이해가 있으면 풀 수 있는 문제이다. 이 개념에 대해서 익숙치 않다면, 친절하게 해설해 놓은 다른 블로그(https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=220820773477&proxyReferer=https%3A%2F%2Fwww.google.com%2F) 를 찾아 보는 것을 추천한다. 

LCA는 부모를 단순히 따라가는 방법을 사용하면 O(N)이지만, Sparse Table이라고 불리는 DP를 사용하면 $O(\log N)$ 에도 해결할 수 있다. Sparse Table을 그대로 구현하면 $O(N\log N)$ 시간 복잡도에 문제를 해결할 수 있으며, "거리 3 이하" 의 조건을 사용하면 단순한 방법을 약간 응용해서 $O(N)$ 시간 복잡도에도 풀 수 있다. Sparse Table 방법을 잘 모른다면 이번 기회에 알아보는 것을 추천한다. 

G. Passport Control

문제가 약간 이해하기 힘든데, 결론부터 말하자면 주어진 수열을 $K$개의 증가 수열로 덮을 수 있는지에 대한 이야기이다. 즉, 수열이 주어졌을 때, 각 수열을 최대 $K$개의 색으로 칠해서, 각각의 색이 칠해진 수만을 보았을 때 그것들이 증가 수열을 이루게 할 수 있는지를 판별하는 것이다. 색과 심사 창구가 일대일 대응이라고 생각하면 비유가 이해가 갈 것이다.

크게 3가지 풀이가 있다.

• 대충 그리디. 가장 생각하기 쉽고 코딩도 어렵지 않다. 다만 증명이 조금 어려울 수 있다. 증가 수열을 순서대로 만들어 나갈 것이다. std::set과 같은 자료 구조에 현재 증가 수열의 맨 마지막 원소를 저장했다고 하자. 하나의 원소 $x$ 를 증가 수열에 뒤에 붙일 때, 증가 폭이 적은 (즉, $x$보다는 작지만 가장 큰) 원소의 뒤에 붙이는 것이 이득일 것이라고 직관을 만들 수 있다. 고로, 그러한 원소를 제거한 후 $x$ 를 삽입하면 된다. 시간 복잡도는 $O(N\log N)$ 언저리이다.
• DAG Path Cover. $i < j, P_i < P_j$ 를 만족하는 $(i, j)$ 쌍에 대해서 $i \rightarrow j$ 방향의 간선을 그어주자. 수열을 $K$개의 증가 수열로 덮는다는 것과, 이 그래프의 모든 정점을 $K$개 이하의 path로 덮는다는 것이 동치가 된다. 이는 이분 매칭으로 구할 수 있다. 자세한 것은 http://koosaga.com/86 참조. 시간 복잡도는 $O(N^3)$ 언저리이다. 
• Dilworth's Theorem. 2번에서 DAG Path Cover 문제로 환원을 했다면 Dilworth's Theorem을 사용할 수 있다. Dilworth's Theorem에 의하면 DAG의 최소 Path Cover는 최대 반사슬의 길이와 동일하다. 이 문제에서 반사슬의 최대 길이는 최대 감소 부분수열(LDS)의 길이와 동일하다. 이는 최대 증가 부분수열 (LIS)와 같은 문제이고, $O(N^2)$ 내지는 $O(N\log N)$ 풀이가 잘 알려져 있다. 이렇게 최대 감소 부분수열의 길이를 구한 후 K 이하인지 비교해 주면 된다. 

Dilworth Theorem은 1번 풀이의 쉬운 증명이 된다. 1번 풀이가 사실은 LDS를 $O(N\log N)$에 구하는 알고리즘과 동일하기 때문이다.

A. Black Chain

이게 블록체인 뭐시기인가... 블랙 고리에서 1을 떼어내는 연산의 횟수 $K$를 정해 두고, $K$번의 연산으로 모든 수를 생성하는 것이 가능한지를 확인해 본다. $K$개의 1을 떼어 내면, 남은 체인들이 최대 $K+1$ 생길 것이다. 이 $K+1$ 개의 수에 $N - K$ 를 적절히 배정해서 조건을 만족시킬 수 있는지를 찾으면 된다.

$K$개의 1만 가지고 만들 수 있는 수는 $\{0, 1, \cdots, K, N - K, N - K + 1, \cdots, N\}$ 이다. 그렇다면 $K+1$번째 수의 첫 항은, 가장 작은 표현할 수 없는 수인 $K+1$ 로 잡아야 한다. 이렇게 되면 양 끝에서 표현할 수 있는 수들의 구간이 커진다. (다음 항이 $2K+2, 4K+4$ 의 꼴로 나올 것이다.) 이를 반복해서 $[0, N]$ 을 전부 덮으면 된다. $K+1$ 개의 수를 다 쓰고도 표현할 수 없는 수가 있으면 답은 불가능이다. 

위 과정을 따라가면 $K \leq \log N$ 정도에서 답이 나온다는 결론을 내릴 수 있다. 고로 $O(\log N)$ ~ $O(\log^2 N)$ 정도에 해결 가능하다.

F. Parcel

먼저 단순한 4중 루프를 생각한다. 모든 $1 \leq i < j < k < l \leq N$ 에 대해서, $A_i + A_j + A_k + A_l = W$ 가 되는 쌍의 존재 여부를 찾고 싶은 것이니, 이를 그대로 코드로 옮기면 된다.

이를 3중 루프로 줄일 수 있다. 모든 $1 \leq j < k < l \leq N$ 에 대해서, $W - A_j - A_k - A_l = A_i$ 가 되는 $1 \leq i < j$ 가 존재하는 지를 찾는 문제로 이를 변환시킬 수 있다. 3중 루프에서 $j$가 증가하면 가능한 $i$의 범위가 하나씩 증가한다. 고로 $j$가 증가할 때마다 $A_i$ 들의 리스트가 자라나게 된다. 이 문제에서는 $W$와 $A_i$가 작기 때문에 이러한 $A_i$를 배열에 저장해 놓을 수 있다. $mark[X] = (i < j, A_i = X$ 인 $A_i$ 가 존재) 라고 하면, 단순히 이 배열에 마킹하고, 이 배열의 원소가 true / false인지를 판별하는 식으로 문제를 해결할 수 있다. 

이를 2중 루프로 줄일 수 있다. 모든 $1 \leq k < l \leq N$ 에 대해서, $W - A_k - A_l = A_i + A_j$ 가 되는 $1 \leq i < j < k$ 가 존재하는 지를 찾는 문제로 이를 변환시킬 수 있다. 2중 루프에서 $k$가 증가하면 가능한 $j$의 범위가 하나씩 증가한다. 고로 $A_i + A_j$ 들의 리스트가 자라나게 된다. 이들을 똑같이 배열에 저장해 나간다. 2중 루프는 당연히 $O(N^2)$에 돌고, $A_i + A_j$의 개수는 많아야 $O(N^2)$ 이니 이들을 마킹하는 데도 그리 많은 시간이 들지 않는다. 고로 시간 복잡도 $O(N^2)$에 문제가 해결된다. 

E. Panokseon

각 partition이 $W$를 넘으면 안 되고, 넘지 않는다면 최소 partition의 크기를 최대화해야 한다. 고로 답에 대한 이분 탐색 접근을 시도할 수 있다. 모든 partition의 크기가 $[W-X, W]$ 구간 안에 들어가게 할 수 있는지를 판별하는 문제를 생각해 보자. 이 문제를 해결한다면 $X \in [0, W-1]$ 구간에서 해당 판별 문제가 참이 되는 최소 $X$를 찾은 후 $X^2$ 를 출력하면 된다.

이 결정 문제는 동적 계획법으로 해결할 수 있다. $DP[i] = ([1, i]$ 구간을 쪼갤 수 있는가) 라고 하자. $sum(i, j) = \sum_{k = i}^{j}{A_k}$ 라 하면 점화식은 다음과 같다. 

$DP[i] = OR_{W-X \leq sum(j + 1, i) \leq W}(DP[j])$ 

(OR 항은 해당 조건을 만족하는 모든 $DP[j]$ 중 참인 값이 하나라도 있으면 $DP[i]$ 가 참이라는 뜻이다.)

부분 배열의 합은 부분 합을 사용해서 깔끔하게 표현할 수 있다. $S_i = \sum_{j=1}^{i}{A_j}$ 라 표현하자. $S_i = S_{i-1} + A_i$ 식을 사용해서 $S_i$ 배열을 선형 시간에 전처리 해 두면,

$DP[i] = OR_{W-X \leq S_i - S_j \leq W}(DP[j])$ 

이렇게 되면 시간 복잡도가 $O(N^2\log W)$ 이고 너무 느리다. $\log X$ 번의 호출이 있기 때문에 이 DP를 $O(N)$ 정도로 최적화해야 할 것이다. 

최적화를 위해서는 두 가지 사실이 필요하다. 첫 번째로, $S_i - S_j \leq W$ 를 만족하는 최소 $j$를 $l$, $S_i - S_j < W - X$ 를 만족하는 최소 $j$를 $r$ 이라고 하자. $i$가 증가하면 이 $l$과 $r$ 도 따라 증가한다. 고로 $l = r = 0$으로 처음에 설정해 둔 후 $i$가 증가함에 따라서 $l, r$을 증가시켜 나가면 $l, r$은 전체 DP 과정에서 $O(N)$ 번만 갱신된다. 이러한 류의 방법을 inchworm / two pointers라 부른다. 이 방법을 사용하면 $DP[i] = OR_{l \leq j < r}(DP[j])$ 와 같이, $i$에 대응될 수 있는 $j$의 구간을 알아낼 수 있다.

두 번째로, $[l, r-1]$ 구간에 참인 DP값이 하나 이상 있는지를 판별하는 것은 위에서 사용한 부분 합을 이용해서 똑같이 할 수 있다. 위 경우에는 DP 배열을 처음에 전부 알지는 못하나, 우리가 알고 싶어하는 구간에 대한 DP값은 모두 알려져 있을 것이다. 고로 DP에 대한 부분합 배열을 DP 계산 과정에서 만들어 나가면 문제를 해결할 수 있다.

K. Suffix-Free Strings

DFA가 Suffix-Free인지 아닌 지를 복잡하게 생각하면 꼬이지만, 사실 Suffix 쌍의 존재 여부를 출력하는 문제라고 생각하면 명료하다. 결국 어떠한 문자열은 DFA 상의 Path에 대응되므로, Suffix 쌍이 존재한다는 것은 DFA 상에서 두 경로 p, q가 존재해서, 둘 다 0에서 시작해서 terminal에서 끝나고, 경로 $p$의 뒤쪽 길이 $length(q)$ 문자열이 $q$의 문자열과 동일함을 의미한다. (일반성을 잃지 않고 $length(p)$ > $length(q)$라 가정)

두 Suffix 쌍 문자열을 찾는다는 것은

 * $p$에서 $length(p) - length(q)$ 길이 prefix를 따라서 어떠한 노드 $V$ 로 이동한 후

 * 해당 노드 $V$와 루트 노드 $0$에서 $length(q)$ 길이의 동일한 문자열을 따라 가서, 둘 다 어떠한 Terminal 노드에 도착

하는 경로를 찾는 것이다. 이 과정에서 해당 문자열이 어떻게 생겼는지는 중요하지 않다. 비어 있지만 않으면 된다. 고로 문제를 완전히 그래프에 두고 생각할 수 있다.

먼저 모든 가능한 $V$의 집합을 찾아보자. 이는 0번 정점에서 시작해서 하나 이상의 에지를 타고 방문할 수 있는 정점들의 집합과 동일하니 단순 DFS로 가능하다. 가능한 $V$를 찾았으면, 두 노드 쌍 $(0, V)$에서 동일한 문자열을 따라가서 두 노드를 모두 Terminal로 보낼 수 있는지를 판별하면 된다. 이는 두 노드 pair를 정점으로 하는 그래프에서 탐색 알고리즘을 돌리면 판별할 수 있다. 시간 복잡도는 $O(NM)$. 

D. Matching

이건 되는지 잘 모르니 간단하게만 서술. 직선의 각도 $\theta$ 가 고정되면 translation을 적당히 해서 distance function의 값을 $max(f(A), f(B))$로 만들어 줄 수 있으니, 결국 문제는 $max(f(A), f(B))$ 를 최소화하는 각도 $\theta$ 를 찾는 문제이다. 이 때, $A, B$가 컨벡스 헐이라고 가정해도 문제가 없다. 컨벡스 헐 안에 있는 점은 distance function에 영향을 주지 않기 때문이다. 

함수 $f(A)$, $f(B)$는 $A$와 $B$의 각 변에 대한 piecewise 삼각 함수 형태로 표현할 수 있다. Rotating Callipers와 같이 $\theta$를 변화시키면서 $f(A)$의 추이를 보자. 만약에 해당 직선이 주어진 볼록 다각형의 변과 만나지 않는다면, 해당 직선이 닿고 있는 두 점만이 $f(A)$ 를 계산하는 데 영향을 준다. 그리고 이 때의 $f(A)$는 삼각 함수로 모델링 할 수 있다. 이렇게 되면 $f(A)$는 $O(N)$ 개의 삼각 함수들의 집합, $f(B)$는 $O(M)$ 개의 삼각 함수들의 집합이다. 

이들 중 최댓값을 계산할 때는, 각 piecewise function이 겹치는 $O(N+M)$ 개의 구간에 대해서 따로 계산해 준 후 이를 합치는 방법을 사용한다. 각 구간에서 위 삼각 함수들은 대략 볼록한 형태를 띄기 때문에, 두 볼록 함수 최댓값의 최솟값은 정의역의 양 끝이거나 두 함수가 만나는 지점이 된다. 이 부분은 수치 계산의 문제가 된다. 이분 탐색으로 열심히 비비면 된다고 들었으나 자세한 디테일은 알지 못하고 알고 싶지도 않다.

더 간단한 풀이가 있다고 생각할 수도 있지만, 확실한 건 정의역의 양 끝만 보는 풀이는 반례가 존재한다.

J. Sliding Blocks

꽤나 깔끔한 풀이가 있다. cki86201이 이에 대해 친절하게 슬라이드를 만들어 주어서, 이를 첨부하는 것으로 풀이를 대신한다.

Jsol.pdf

C. Lucid Strings

풀이 모름. 대회장에서는 Naive 알고리즘에 가까운 $O(N^2 / K)$가 뚫렸다고 한다. 아마 K = rand() % (N - 1) + 2 하신 듯 하다. 물데이터 꺼억~

+ 예비소집때 검증해 봤는데 N / K <= 50 assertion이 통과했다. $O(N^2logN / K)$ 도 이상없음 (꺼억)