ACM-ICPC Seoul Regional 2018

(2018.11.10: H를 제외한 모든 풀이를 작성하였다.)

(2019.07.05: I 문제를 Chordal Graph로 푸는 방법에 대한 간단한 부연설명을 추가하였다.) 
 

Result Analysis

이번 서울 리저널에서의 각 대학 별 상위 팀은 다음과 같다.

• 서울대학교: 789 (순위 외: 2018 WF 은메달)
• 도쿄대학교: Gifted Infants (순위 외: 2018 WF 금메달)
• KAIST: Deobureo Minkyu Party (리저널 1등)
• 국립 타이완 대학교: waynedisonitau123 (리저널 2등)
• 한양대학교: FailedSystemTest (리저널 3등)

시상식을 대회 후에 진행해서 엄청나게 김이 빠졌지만... 올해 리저널은 작년에 비해서 흥미로운 결과가 여럿 있었다.

• 서울대학교 내전. 789와 Black Cow 모두 평소 연습에서 아주 강한 결과를 보여준 바가 있다. 하지만 Black Cow의 평소 실적이 매우 훌륭했기 때문에, 적어도 나는 올해의 교내경쟁이 2016년과 비슷한 양상을 띌 것이라는 데에 별 의문을 갖지 않았다. 대회 초중반을 거치면서 Black Cow는 789를 계속 압도했으나, 789가 빠르게 따라잡았기 때문에 그 차이가 크지는 않았다. 두 팀 모두 3시간 즈음에 10문제를 완성한 상태에서 후반부로 대회가 접어들었다. 한 문제만 해결하면 이때까지의 승부를 모두 원점으로 돌릴 수 있는 상황에서, 789는 대회 종료 6분 전에 I번 문제를 풀어냈고, 기존의 승부를 원점으로 돌리고 승리를 거머쥐었다. 축하합니다!
• 외침. 올해의 강한 해외팀은 동경대의 Gifted Infants, NTU의 waynedisonitau123 이 있었다. Gifted Infants는 평소 다양한 프로그래밍 대회에서 매우 강한 성적을 보여왔던 yosupo, sigma425, maroonrk로 이루어졌고, 올해 WF 메달 가능성이 아주 높은 팀이다. 3등이라는 성적이 절대적으로 높지는 않으나, 올해 서울대의 결과가 매우 강했음을 감안하면 충분히 훌륭한 성적으로 보인다. waynedisonitau123은 Lazy Propagation을 사용하는 문제였던 A를 20분에 First Solve 함으로써 멘붕을 안겨주고, 찍어맞추는 유형의 문제인 C를 140분에 First Solve 함으로써 다른 팀들이 같이 찍어맞출 용기를 주었다. 최종 성적은 5등이지만 스코어보드에 준 영향은 상당히 컸다고 생각한다. Congratulations!
• 한양대학교 는 매년 ICPC에서 꾸준히 좋은 성적을 내온 대학 중 하나지만, 올해 대회에서는 9문제를 해결하고 리저널 3등 성적을 냄으로써, World Finals에 진출할 가능성을 확보하였다. 최근 몇년간 리저널 3등 이내에 든 학교는 거의 KAIST / 고려대 / 서울대로 한정되어 있었고, 예외는 kriii님이 있던 성균관대와 2017년의 UNIST 정도였는데, 올해 서울 리저널에서는 한양대학교가 이 리스트에 새롭게 이름을 올렸다. 이후 해당 팀의 해외 리저널 성적과, 다른 대학의 해외 리저널 성적이 이 팀의 운명을 좌우할 것이다. 그러니까 이제 한동안 해외 리저널 보면서 발을 동동 구를 일만... 축하합니다!

My story

작년 팀원들과는 호흡이 상당히 잘 맞았기 때문에 팀을 깰 생각이 없었다. 혜아가 World Finals를 두번 나가서 다시 출전을 하지 못하는 게 문제였다. 올해 초 여러 복잡한 사건들을 거치면서 내년에는 수찬이와 WF에 가야겠다는 생각을 했다. 그래서 수찬이에게 WF가면 내년 동아리 회장하는 조건으로 (...) 팀원을 제안했고, 수찬이가 받아줘서 그렇게 했다.

팀 이름에는 만족하고 있었으나, 최근 지지율이 떨어지기도 했고 2년 하기에는 약간 식상해서 바꿀 생각이 있었다. 그래서 2시간 정도 회의를 했는데, 재미가 없거나, 지나치게 정치적으로 올바르지 못하다는 이유 등으로 탈락하였다. 좋은 대안을 못 찾아서 그대로 유지.

인터넷 예선 전후 성적을 보면서, WF에 나갈 수 있을 지 없을 지는 몰라도 이대로라면 나가면 안되는 실력이라는 생각이 들었다. 그래서 학기중 바쁜 와중에 매우 밀도있는 팀연습을 진행하였다. 셋 다 몇번 참교육 당하더니 폼이 금방 올라왔다. 지금은 WF에 나가서도 잘 할 것 같다. 😄

Problemset

인터넷 예선과 17 대전 리저널 이후 모두의 예상을 깨고 (...) 문제 셋의 수준이 꽤 높게 나왔다. 16년도 대전 리저널과 비교할 수 있다고 생각한다. 문제는 난이도 순으로 정렬했다. 정확히 난이도 순으로 정렬했다고 생각하지만, 이견이 있을 수 있다.

D. Go Latin (☆)

단수형 라틴어 단어가 주어졌을 때 복수형 라틴어 단어로 변환하는 문제로, 문제에 규칙이 다 나와있기 때문에 이를 구현하면 되는 단순 구현 문제였다. 기초적인 문자열 조작 능력이 있으면 쉽게 풀 수 있으나, 규칙이 여러가지이기 때문에 실수하지 않는 코딩을 하고, 오타를 내지 않는 것이 핵심이다.

L. Working Days (★☆)

첫날부터 순서대로 일을 배정한다고 해 보자. 첫 날에는 모든 사람들이 일을 할 수 있는데, 이 중 누구를 골라서 일을 시켜야 할까? 직관적으로 생각해 보면, 가장 할 일이 많은 사람이 첫 날부터 바쁘게 일을 해야 할 것이다. 그렇다면, 가장 할 일이 많은 $a_1$ 명의 사람들에게 일을 시키고. 다음 날로 넘어가자. 다음 날에는 몇명의 사람들은 일을 하거나 쉬는 상황일 것이다. 고로 이러한 사람들을 빼고 가장 할 일이 많은 $a_2$ 명의 사람들에게 일을 시키고...

위와 같은 생각을 연장시키면 단순한 Greedy 전략을 생각해 볼 수 있다. 첫날부터 순서대로 움직이면서, 현재 일 할 수 있는 사람들 중 할 일이 가장 많은 $a_i$ 명의 사람을 골라서 이들에게 일을 시키는 것이다. 실패가 있다면 (사람이 부족하거나 이렇게 해도 일을 다 못하거나) 답은 없는 것이고, 실패가 없다면 이대로 진행하면 된다.

이를 단순하게 구현하면, 각 날에 대해서 일이 많은 $a_i$ 명의 사람을 $O(N\log N)$ 정렬 후 찾을 수 있다. 이 방법의 시간 복잡도는 $O(NM\log M)$ 이다. 정렬은 매우 빠르기 때문에 이러한 단순 구현으로 충분히 AC를 받을 수 있다. 굳이 필요하지 않지만, $a_i \leq N$ 임을 응용해서 Counting Sort를 하면 시간 복잡도에서 log를 없앨 수 있다.

틀릴 수 없어 보이는 이 Greedy는 실제로도 아주 잘 된다. 증명은 일반적인 Exchange Argument인데 여기서는 짧게만 설명한다. 위 Greedy가 틀렸다고 가정하자. 그렇다면, 위 Greedy가 답을 못 찾지만 답이 있는 경우가 존재한다. 실제 답 전략과 Greedy가 다르게 동작하는 마지막 날을 생각해 보자. 이 날 선택되지 않은 일이 가장 많은 사람 $x$, 이 날 선택된 일이 가장 적은 사람 $y$를 고려했을 때, 위 Greedy가 틀렸다는 가정에 의해 $x$의 남은 일의 개수 $D_x$가 $y$의 남은 일의 개수 $D_y$ 이상이다. 이 때, 단순히 $x$의 차후 일 목록과 $y$의 차후 일 목록을 그냥 교환하고, $y$의 차후 $D_x - D_y$ 개의 일을 $x$한테 다시 몰아주자. "마지막 날" 이라는 가정 때문에, 위와 같은 교환은 항상 가능하다. 이를 반복하면 이 "마지막" 날까지의 답 전략을 Greedy한 전략으로 대체할 수 있다. 이를 날짜를 줄여가며 계속 반복하면 (수학적 귀납법) Greedy 전략도 답이 있다는 결론에 도달해서, 가정에 모순이다.

F. Parenthesis (★☆)

수식이 주어졌을 때, 이 수식이 올바른 C-style 수식인지를 판별하고, 만약 그렇다면 이 수식이 올바르게 괄호가 쳐진 수식인지를 확인하는 문제이다.

먼저, 수식이 올바른 C-style 수식인지 아닌지 (error인지 아닌지) 부터 해결하자. 수식이 무엇인지를 엄밀하게 정의하는 것이 도움이 될 것이다. 괄호 문자열과 비슷하게, 수식은 다음과 같이 재귀적으로 정의된다.

• 한 글자 심볼은 올바른 수식이다.
• $E1$과 $E2$ 가 올바른 수식이면, $E1$ op $E2$ (op는 사칙연산자) 는 올바른 수식이다.
• $E1$이 올바른 수식이면, $(E1)$ 역시 올바른 수식이다.

어떠한 수식이 이 재귀적 정의 안에 들어가는 지를 판별하는 것은 어떻게 할 수 있을까? 후위표현식 변환과 비슷하게 Stack을 사용하여 선형 시간에 하는 방법이 잘 알려져 있으나, 더 간단한 방법도 있다. 주어진 수식을 토큰으로 분할하고, 다음 과정을 반복하자.

• 심볼 x, y와 사칙연산자 op에 대해, x op y 과 같은 패턴이 있다면, x로 대체한다.
• 심볼 x에 대해, (x) 와 같은 패턴이 있다면, x로 대체한다.

이는 위 재귀적 과정에 따라서 수식의 크기를 하나씩 줄여나가는 것이라고 생각할 수 있다. (스택을 사용하여 문제를 해결하는 것 역시 위 과정과 근본적으로 동일하다.) 최후에 하나의 심볼이 남는다면 수식은 error가 아니고, 그렇지 않다면 수식은 error이다.

위와 같은 방법을 사용하면 proper / improper의 판별도 똑같이 할 수 있다. 이 경우에는 제약 조건이 붙어서 더 간단하다. 심볼 x, y와 사칙연산자 op에 대해서, (x op y)와 같은 패턴이 있다면 이를 x로 대체하는 것을 반복하자. 최후에 a op b가 남았다면 이는 proper한 수식이고, 그렇지 않다면 improper한 수식이다. 이 때, "a"도 proper함에 유의하라. 시간 복잡도는 $O(n^2)$로, 문제를 풀기 충분하다.

K. TV Show Game (★★)

3개의 조건 중 2개의 조건을 만족하는 문제 대신, 2개의 조건 중 1개의 조건을 만족하는 문제를 풀어보자. 이 문제는 잘 알려진 2-SAT 문제로, $n$개의 boolean value $p_1, p_2, \cdots p_n$ 을 만든 후, $p_i$ 가 참이면 파란색, 아니면 빨간색으로 색을 칠한다고 하자. 이제 문제에 주어진 모든 조건을 2-CNF 식으로 그대로 변형시킬 수 있다. 2-SAT 문제는 선형 시간 해결 방법이 잘 알려져 있고 이 단락에서는 설명하지 않는다.

이제, 원래 문제로 돌아오자. 3개의 조건 중 2개 이상을 만족시킨다는 조건을 그대로 적용할 수는 없지만. 위 제약된 형태가 2-SAT 문제이니 이 문제도 2-SAT으로 변형하면 된다는 강한 느낌을 받을 수 있다. 실제로, 간단한 변환으로 이를 2-CNF 형태로 만들 수 있다. 논리 식 $a, b, c$ 중 2개 이상이 만족한다는 것은, $a \lor b$, $b \lor c$, $c \lor a$ 가 모두 만족된다는 것과 동치임을 확인할 수 있다. 즉, 각 줄에 있는 조건은 결국 3개의 2-SAT 항으로 변형된다. 이 2-SAT을 해결하면 문제를 해결할 수 있다.

A. Circuits (★★☆)

축에 평행한 직사각형 $n$개가 주어져 있을 때, $x$축에 평행한 직선 2개를 그어서 최대한 많은 직사각형을 교차시키는 문제이다. 긋는 직선이 $x$축에 평행하니까 당연하게도(...) 직사각형의 $x$좌표는 전혀 중요하지 않고 입력으로 받을 필요도 없다. 결국 문제는, $n$개의 구간이 주어졌을 때, 점 2개를 찍어서 최대한 많은 구간을 교차시키는 것이다.

먼저 해야 할 관찰은, 찍는 점이 어떠한 구간의 끝점 중 하나라고 가정할 수 있다는 것이다. 만약에 찍는 점이 어떠한 구간의 끝점도 아니라면, 이를 끝점이 나올 때까지 왼쪽으로 밀어줘도 상관이 없다. 이렇게 될 경우 가능한 후보가 유한하게 ($O(n^2)$) 로 줄고, 좌표 압축의 논리를 활용할 수 있다는 장점이 있다. 이 상태에서 구간을 좌표압축하고 모든 끝점의 쌍을 시도하면 $O(n^3)$ 알고리즘을 유도할 수 있다.

여기서 문제를 해결할 수 있는 두가지 관점이 있다. 두 관점에 따라서 유도되는 결론은 동일하지만, 이 문제에서는 여러가지 관점을 익히는 것이 매우 중요하다고 생각한다. 고로 둘을 모두 소개한다.

점 하나를 고정: 찍은 점 중 하나를 고정시키면 문제를 해결할 수 있을까? 고정한 점을 $p_1$이라고 하자. $p_1$을 포함하는 구간은 모두 교차되었기 때문에 이후 고려하지 않아도 된다, $p_1$을 포함하지 않는 구간들에 대해서, $p_2$를 찍어야 하는 위치는 이들이 가장 많이 교차하는 위치일 것이다. 결과적으로, 우리는 $p_1$을 포함하지 않는 구간이 최대 몇개 동시에 쌓여있는가에 대해 관심이 있다.

이를 자료구조를 통해서 해결해 보자. 구간에 일정한 수를 더하고, 전체 최댓값을 계산할 수 있는 자료구조가 있으면, 우리는 구간들을 모두 더해주고 최댓값을 계산함으로써 문제를 풀 수 있다. 이는 Lazy Propagation을 사용한 Segment Tree를 통해서 해결할 있다. 이 때의 시간 복잡도는 $O(n^2\log n)$ 이다.

여기서 낭비가 되는 부분은, $p_1$을 바꾸는 시점에서 우리가 전체 구간들을 전부 순회한다는 것이다. $p_1$을 순서대로 증가시키면서 해결한다고 생각해 보자. 어떠한 구간 $[s, e]$는 $p_1 < s$일 때는 $p_1$과 교차하지 않다가, $s \leq p_1 \leq e$일 때 $p_1$과 교차하고, $e < p_1$일 때 다시 교차하지 않는다. 고로, $p_1$이 고정되어 있을 때 우리는 굳이 전체 구간을 돌 필요 없이, $p_1 - 1$ 상태에서 변화한 구간들만 갱신시켜 주면 된다. 이렇게 되면 구간이 추가되고 제거되는 이벤트가 총 $2n$개이고, $p_2$는 위에서 만든 Segment Tree를 그대로 관리해 주면 바로 찾을 수 있다. 시간 복잡도는 $O(n\log n)$ 이다.

기하학적 접근: $f(p_1, p_2)$ 를, $p_1, p_2$ 에 점을 찍었을 때 교차하는 구간의 개수라고 정의하자. 우리는 모든 $1 \leq p_1, p_2 \leq 2n$ 에 대해서 $f(p_1, p_2)$ 의 최댓값을 계산하고 싶다. 구간 $[s, e]$가 $f(p_1, p_2)$ 에 기여한다는 것은:

• $p_1 < s$ 라면, $s \leq p_2 \leq e$ 이어야 이 구간이 $(p_1, p_2)$ 와 교차한다.
• $s \leq p_1 \leq e$ 라면, $p_2$와 상관없이 구간은 교차하니, $1 \leq p_2 \leq 2n$ 이어야 이 구간이 이 구간이 $(p_1, p_2)$ 와 교차한다.
• $e < p_1$ 이라면, $s \leq p_2 \leq e$ 이어야 이 구간이 $(p_1, p_2)$ 와 교차한다.

$x$ 축을 $p_1$, $y$ 축을 $p_2$로 가지는 격자점에 $f(p_1, p_2)$ 를 적었다고 하자. 어떠한 구간 하나가 추가되었을 때, $f(p_1, p_2)$는 이 구간과 교차하는 점들에 대해서 +1이 되고 그렇지 않은 점들에 대해서 0이 된다. 이 때, 구간과 교차하는 점들의 집합은 3개의 겹치지 않는 직사각형으로 표현할 수 있다. 요컨데 $n = 5, [s, e] = [3, 5]$ 라고 하면 (행렬처럼 아래/오른쪽으로 갈수록 $x, y$ 증가)

XXOOOXXXXX

XXOOOXXXXX

OOOOOOOOOO

OOOOOOOOOO

OOOOOOOOOO

XXOOOXXXXX

XXOOOXXXXX

XXOOOXXXXX

XXOOOXXXXX

XXOOOXXXXX

와 같은 그림이 나올 것이다. O와 겹치는 위치는 +1이 더해질 것이고, 그렇지 않은 위치는 그대로 남을 것이다.

우리가 알고 싶은 것은 $f(p_1, p_2)$ 의 최댓값이다. 고로, 위에서 만든 $3n$ 개의 직사각형 중 가장 많은 직사각형이 겹치는 위치를 알고 싶다. 이는 Plane Sweeping을 통해서 풀 수 있음이 잘 알려져 있다. 고로 위에서 만든 것과 똑같은 Segment Tree를 만들면 $O(n\log n)$ 시간에 문제를 해결할 수 있다.

여담으로, 이 문제는 $k$개의 점을 찍는 경우에도 $O(kn\log n)$ , 심지어는 $O(n\log^2 n)$ 시간 복잡도에 해결할 수 있다.

J. Starwars (★★☆)

올해 인터넷 예선 K와 거의 동일하지만, 제한이 작아서 조금 더 쉬워졌다는 차이가 있다. 문제가 길어서 읽기 힘들지만, 읽고 나면 이 문제는

• 어떠한 인간 정점에서 어떠한 기지 정점에 도착하는 경로 $P$
• 어떠한 외계인 정점에서 어떠한 기지 정점에 도착하는 경로 $Q$
• $P$에 적힌 알파벳과 $Q$에 적힌 알파벳이 동일

둘이 출발하는 인간 정점과 외계인 정점을 고정시키면, 두 정점이 같은 수가 적힌 에지를 계속 반복해서 고르면서, 서로 기지 정점에 도착할 수 있는가를 찾는 문제이다. 이는 노드 쌍을 정점으로 하는 깊이 우선 탐색을 구현하면 된다. 현재 보고 있는 정점 쌍이 $(p, q)$ 라면, $p$에 인접한 모든 정점, $q$에 인접한 모든 정점을 보면서, 해당 정점과 연결된 간선이 같은 수가 젹혀있다면 그 간선을 동시에 타고 가서 이동하는 것이다.

둘이 출발하는 정점의 쌍이 여러가지일 수 있으나, 그냥 Flood Fill 하듯이 도달이 될 때까지 모든 쌍을 다 해보면 된다. 아니면, 인간 더미 정점과 외계인 더미 정점을 만든 후, 각 더미 정점에서 대응되는 인간 / 외계인 정점에 대해서 번호 1이 붙어있는 에지를 다 만들어 줘도 된다. 이러면 (인간 더미 정점, 외계인 더미 정점) 에서 한번만 DFS를 해도 문제가 해결된다.

시간 복잡도는

$O(\sum_{i \in V(G)}{\sum_{j \in V(G)}{(deg_i \times deg_j)}}) = O(\sum_{i \in V(G)}{deg_i \times \sum_{j \in V(G)}{deg_j}}) = O(M^2)$

이다.

E. LED (★★★)

E는 절대적으로는 쉬운 편인 문제에 속하나, 문제에 숨겨져 있는 이상한 함정을 찾는 것이 아주 까다로운 문제였다. 출제 의도를 이해하기 힘든 문제라고 생각한다 (꼼꼼한 건 나름대로 중요하긴 하나..).

최댓값을 최소화하는 것이니 답에 대한 이분 탐색을 사용해야 한다는 생각이 든다. $D$ 이하의 답이 있는지를 판별해 보자. 결국 각각의 점에 대해서 $L_i - D \leq F(v_i) \leq L_i + D$를 만족하는 함수 $F$ 를 찾아야 하는 문제이다. 이는 $n$ 개의 구간이 있을 때, 문제에서 주어진 형태의 함수 중 이 구간을 모두 지나는 함수가 있는지를 판별하는 문제와 동일하다.

이는 Greedy하게 할 수 있다. 모든 주어진 데이터를 $v_i$ 순으로 정렬하자. 함수의 상태는 크게 3개의 phase가 있다고 해석할 수 있다. phase를 바꾸는 것은 비가역적이니 문제를 해결할 때 현재 함수의 값을 최대한 유지하는 것이 좋다. 즉, $L_i \leq D$ 를 만족할 때까지는 첫번째 phase를 그대로 유지한 후, 현재 phase로는 도저히 그것이 불가능 할 때 구간을 위로 올리고, 그것이 또 불가능해지면 구간을 올리고... 이를 3번 해 본 후, 모든 점이 덮였는지를 보는 것이다.

$L_i \leq D$ 를 만족하지 않아서 첫번째 phase를 깨뜨려야 하는 상황을 생각해 보자. 해당 위치를 포함해서, 그 뒤에 있는 모든 값들 중 최솟값을 생각해 보자. 두번째 phase의 함수값은 이것에 $D$ 를 더한 것보다 무조건 작거나 같아야 한다. 하지만 이보다 작을 이유는 없으니, 이것의 최솟값 + $D$ 를 두번째 phase의 함수값으로 설정한다. 두번째 phase를 깨뜨릴 때도 비슷한 방법으로, 아직 덮이지 않은 점의 $L_i$ 최솟값 + $D$를 함수값으로 설정해 준다. 이를 반복해서 최후에 모든 점이 덮였는지 아닌지를 체크한다. $D$ 는 반정수이기 때문에, 모든 $L_i$ 를 2배 해준 후, 정수라고 가정하고 이분 탐색을 하면 문제가 해결되.. 었을까??

이를 그대로 구현하면 Wrong Answer를 받는다. 반례는 다음과 같다:

1

0 10000

답은 놀랍게도 10000.0 이다. 그 이유는, 첫번째 phase를 0인 위치에서 절대 깨뜨릴 수 없게 문제 디스크립션이 써져있기 때문이다 (부등호를 잘 보자!) 고로, 이에 대해서 특수한 예외 처리가 필요하다. 다행이도, 이 예외처리는 크게 복잡하지 않다. $v_i = 0$ 인 점이 있으면 이 점에 대해서만 예외처리를 해 주면 되기 때문에, 이 때 단순히 이분 탐색의 시작 범위를 $L_i$ 로 설정해 주면 된다. 이를 해결하면 정답을 받을 수 있다.

B. Cosmetic Survey (★★★)

문제에서 요구하는 것이 꽤 복잡하게 써져 있다. 순서대로 하자.

• 일단 문제에서 하라는 대로 따라하면 $d(x, y)$를 구해놓을 수 있다. 문제에서 정의하는 Path는 일반적인 그래프와 똑같은데, $d(x, y) > d(y, x)$일 경우에만 $x \rightarrow y$ 간선이 있는 꼴이니 이 때에만 간선을 만들어 줘야 한다.
• Path의 Preference Index는 Path 상에 있는 모든 간선의 $d(x, y)$ 값 최소다. 우리는 가능한 $X \rightarrow Y$ 경로 중 Preference Index의 최댓값을 $S(X, Y)$ 라고 정의한다. 경로가 없으면 $S(X, Y) = 0$ 이다.
• 이걸 모든 $X, Y$ 에 대해 구해놓으면 문제에서 하라는 대로 답을 찍을 수 있는 것 같으니, 이것을 각 쌍에 대해서 구하는 것이 목표이다.

이제 문제는 다음과 같이 간략하게 표현 가능하다:

• 방향성과 가중치가 있는 그래프 $G$가 주어졌을 때, 모든 정점 쌍 $X, Y$ 에 대해서, 가능한 모든 $X \rightarrow Y$ 경로 중 간선 가중치의 최솟값을 최대화한 값을 구하라.

이는 최단 경로 알고리즘을 응용해서 해결할 수 있다. Dijkstra 알고리즘도 충분하지만, Floyd-Warshall 알고리즘을 사용하면 구현과 이해가 쉽다. 초기 행렬을 $D[i][i] = \infty$, $D[i][j] = 0 (i \neq j)$ 라고 설정하자. Floyd-Warshall의 요령을 그대로 활용해서, $i \in [1, N]$ 와 모든 $1 \leq j, k \leq N$ 에 대해, $i$번 정점을 거치는 $j \rightarrow k$ 경로 중 최솟값을 최대로 하는 경로를 찾는다. 이 경로의 값은 $min(D[j][i], D[i][k])$ 이다. 이를 $j \rightarrow k$ 로 가는 경로의 최댓값에 업데이트하는 것을 계속 반복해 주면 된다.

G. Secret Code (★★★☆)

문제를 다음과 같이 변형할 수 있다.

• $[0, S]$ 구간 안에 3개의 점 $p_a, p_b, p_c \in [0, S]$ 를 고른다 (이 점이 정수일 필요는 없다).
• 각각의 점에서 시작해서 길이가 $w_a, w_b, w_c$인 구간을 3개 긋는다. 즉, $[p_a, p_a + w_a], [p_b, p_b + w_b], [p_c, p_c + w_c]$ 와 같은 3개의 구간이 있는 것이다.
• 이 3개의 구간들을 시작점 순으로 정렬하였을 때, 시작점이 가장 작은 구간과 두번째로 작은 구간이 겹치고, 두번째로 작은 구간과 세번째로 작은 구간이 겹치기를 원한다.
• 모든 가능한 $p_a, p_b, p_c \in [0, S]$ 중 원하는 상황이 일어날 확률을 구해야 한다.

여기서, 우리는 $p_a \le p_b \le p_c$라고 가정할 수 있다. 그렇지 않은 경우의 확률 역시 세어 줘야 하지만, 이는 거꾸로 모든 가능한 $\{w_a, w_b, w_c\}$의 순열을 돌면 해결할 수 있기 때문이다.

위 가정 덕분에 우리가 원하는 사건을 부등식으로 쓸 수 있다. 가장 작은 구간과 두번째로 작은 구간이 겹친다는 것은 $p_b \leq p_a + w_a$ 를 뜻하고, 두번째와 세번째가 겹침은 $p_c \leq p_b + w_b$ 를 뜻한다. 즉, 우리는 모든 $0 \leq p_a \leq p_b \leq p_c \leq S$ 인 사건 중, $p_b \leq p_a + w_a$, $p_c \leq p_b + w_b$ 를 만족할 확률을 구해야 한다.

식이 참 복잡하니, 조금 정리해 주자. $a = p_a, b = p_b - p_a, c = p_c - p_b$ 라고 정의하면, 결국 $a, b, c \geq 0, a + b + c \leq S$ 인 모든 사건 중, $b \leq w_a, c \leq w_b$ 를 만족할 확률을 계산하는 것이 된다.

정리된 식은 간단할 뿐만 아니라, 기하적인 관찰을 가능하게 한다. $(a, b, c)$ 를 3차원 좌표평면에 편다면, 결국 우리가 계산할 것은, 원점을 중심으로 하는 사각뿔과, 원점을 한 꼭짓점으로 하는 직육면체의 교집합의 넓이를 계산하는 것이다. 초등/중학교 때 배운 공식 $V = \frac{1}{3}Ah$ 를 사용하면 (아니면 고등학교때 배운 적분을 쓰면) 사각뿔의 부피가 $\frac{1}{6}S^3$임은 쉽게 보일 수 있다. 그렇다면 사각뿔과 직육면체의 교집합은 어떨까? 매우 복잡하지 않을까?

사각뿔과 직육면체의 교집합을 계산하는 것은 포함 배제를 사용하면 간단하다. 전체 사건의 부피가 $\frac{1}{6}S^3$ 인 것은 알고 있으니, 여기서 $b$가 잘못된 경우의 부피를 빼고, $c$가 잘못된 경우의 부피를 빼고, 둘 다 잘못된 경우의 부피를 더하자. 예시로 $b, c$가 모두 잘못된 경우를 생각해 보자. $b \geq w_a, c \geq w_b, a \geq 0$ 임과 동시에 $a + b + c \leq S$ 인 부피를 알고 싶은 것인데, 이는 $a, (b - w_a), (c - w_b) \geq 0, a + (b - w_a) + (c - w_b) \leq S - w_a - w_b$ 라는 식과 동일하다. 즉, 위와 동일한 식이다! 이런 식으로 각 경우에 대한 부피를 간단하게 계산할 수 있고, 이들을 다 합해주면 답을 찾을 수 있다.

C. Disks Arrangement (★★★★)

최댓값과 최솟값이 4배 이하의 차이를 가진다는 조건 때문에, 두 원이 만나는 복잡한 경우를 가정할 필요가 없다. 원을 수직선과 닿는 순서대로 읽었을 때, 어떠한 원은 그 원의 왼쪽 / 오른쪽에 있는 원과만 인접할 수 있다. 이제 피타고라스의 정리를 사용해서 순서가 고정되었을 때의 답을 단순 수식으로 정리할 수 있다. 반지름의 순서를 $r_1, r_2, \cdots, r_n$ 이라 했을 때, 답은 $r_1 + \sum_{i = 2}^{n}{2\sqrt{r_{i-1}\times r_i}} + r_n$ 이 된다. 이제 우리는 주어진 반지름을 적당히 섞어서 위 식을 최소화해야 한다. 일반성을 잃지 않고 주어진 수열은 정렬되어 있다고 하자.

근호가 들어가니 찾고 싶은 성질이 찾을 수 있는 성질이 보이지 않는다. 일단은 짜증나는 근호를 한번 빼 보긴 하자. 답을 $ \sum_{i = 2}^{n}{(2r_{i-1}\times r_i)}$ 라고 하자. 네 실수 $a \leq b \leq c \leq d$ 에 대해 $ab + cd \geq ac + bd$ 이기 때문에, 이 때의 답은 대충 $r_1, r_n, r_2, r_{n-1} \cdots, r_{n/2}$ 과 같이 큰 수와 작은 수를 반복하는 형태를 띔을 알 수 있다. 조금 더 구체적으로 들어가면 $r_1, r_n, r_3, r_{n-2}, \cdots, r_{n/2}, \cdots, r_{n-3}, r_4, r_{n-1}, r_2$ 와 같은 식으로 쓸 수도 있겠다. 이런 식의 construction이 조금 더 작은 답을 준다.

직감적으로는 대충 위와 같은 식이 근호가 있는 상황에서도 큰 답을 줄 것 같으나, 증명을 하라 그러면.. 아이고. 심지어 4로 나눈 나머지에 따라서 케이스가 갈리는 저 더러운 패턴이 정확한지조차도 의심된다. 하지만 스코어보드에서 풀려 있으니, 답은 쉬운 곳에 있다고 생각해 보자. 랜덤 데이터에 대해서 백트래킹을 돌려보면, 위에서 나온 construction과 매우 유사한 패턴만이 답으로 출력된다. 이 패턴이 답을 만들어 내는 유일한 경우의 수일까? 대회에서 AC를 받은 팀들과, 이 논문에 따르면 (Theorem 6) 그렇다고 한다. 논문의 증명은 읽어보지 않았기 때문에 더 이상의 자세한 설명은 생략하고, 정확한 패턴은 직접 백트래킹을 돌려서 찾아보거나 논문을 읽어보도록 하자.

여담으로, 제약 조건이 없는 케이스는 BOJ에도 있는 잘 알려진 문제이다. 해당 문제는 NP-complete인데, 이 문제에 대한 4/3-approximation 알고리즘이 있다고 한다. 관심이 있다면 위 논문을 읽어 보는 것도 좋을 것 같다.

I. Square Root (★★★★★)

Bottom-up으로, 트리를 리프에서 루트로 순서대로 만들어 나가는 전략을 취한다. 일단. 충분히 큰 rooted tree에서 트리의 리프를 순서대로 발견하는 방법을 생각해 보자. 여기서 "인접하다" 라고 함은 트리 상의 거리가 2 이하임을 뜻한다. 즉 이는 자신을 포함한다. 어떠한 정점 $v$ 에 대해서 $v$ 와 인접한 정점 집합을 $N(v)$ 라 표현한다.

• Case 1: $|N(v)| = 3$ 인 정점이 존재한다. 트리가 존재한다면, $v$는 리프이고, $v$의 부모의 차수가 2일 것이다. 이 정점을 제거하고 계속 귀납적으로 진행한다.
• Case 2: 그런 거 없다. 이는 트리 상에 존재하는 모든 리프의 부모의 차수가 3 이상임을 뜻한다. 이 중 가장 깊이가 큰 리프를 한번 보자. 이 리프의 부모에는 여러 개의 리프들이 달려 있을 것이며, 이 리프들은 모두 인접한 정점들의 집합이 동일하다는 성질을 가진다. 그렇다면, $N(v)$가 동일한 정점들은 모두 하나의 부모를 공유하는 리프일까? 트리가 충분히 크다는 가정하에 그렇다. 고로, $N(v)$ 가 동일한 정점 집합을 아무거나 찾은 후, 한꺼번에 제거해 주면 된다. 트리라면 무조건 저러한 집합이 존재한다.

위 가정들은 트리가 대부분의 인자에 대해서 충분히 큰 값을 가지고 있음을 가정하니, 현실적인 경우에서 발생하는 degenerate case를 전혀 고려하지 못한다. 엄밀하게 보정하면, 트리의 지름이 4 이상일 때 항상 저 둘 중 한 경우가 만족함을 알 수 있다. 여기서 대략 알고리즘의 outline을 잡을 수 있다. 트리의 지름이 4 이상이라면, 임의의 리프(들)을 잡아서 제거하고, 지름이 3 이하일 때는 예외 처리로 일일이 트리를 구한 후, 이 둘을 적당히 합쳐서 트리를 찾는 것이다. 이 과정 중에서 이상한 것이 하나라도 있거나, 만든 트리의 제곱을 찾았을 때 이것이 입력과 매치가 되지 않는다면, 주어진 그래프는 Tree Square가 아니다.

트리의 지름이 3 이하인 경우의 예외 처리는 다음과 같이 진행하면 된다.

• 트리의 지름이 1인 경우는 자명하다.
• 트리의 지름이 2인 경우는 성게(star graph)밖에 없다. 이 경우는 입력이 완전 그래프일 경우 발생한다.
• 트리의 지름이 3인 경우는, 두 정점을 잇는 에지 하나와, 이 두 정점에 연결된 여러 개의 정점과 같은 입력이다 (즉, 성게 2개가 간선으로 붙어 있음). 이 경우 직접 연결되어 있지 않은 임의의 두 정점 쌍 $u, v$ 를 잡는다. $u$와 인접하지 않은 모든 정점을 $S_1$, $v$와 인접하지 않은 모든 정점을 $S_2$ 라 하자. 남은 두 정점은 간선을 이루는데, 두 정점의 집합이 같기 때문에 이를 분리할 수 있는 방법이 없다. 고로 트리를 둘 다 시도해본 후, 제곱이 입력인 트리가 있으면 그거를 출력하고, 없으면 Tree Square가 아니라고 하면 된다.

이제 전체 알고리즘으로 돌아오자.

• 지름이 1, 2인 경우 입력 단에서 잘라준다.

• 지름이 4 이상일 때까지, 리프를 반복적으로 떼어 나간다, 그리고 그 순서를 관리한다. 이 과정에서 정점의 개수는 확실히 감소하고, 지름의 길이는 1 감소하거나 감소하지 않는다. 고로, 최종적으로 지름이 3인 트리가 남을 것이다. 이 때, 지름이 3인지 아닌지는, $N(v) = V(G)​$ 인 정점의 개수로 판별할 수 있다. 이것이 2개 이상이면 지름이 3 이고, 아니면 지름이 4 이상이다.

• 지름이 3일 경우, 위에 있는 예외처리로 $S_1, S_2$ 를 찾는다. 이들을 트리에서 순서대로 "떼어준다". 마지막 두 정점 $v_1, v_2$의 순서는 둘 다 시도해 본다.

• 지름이 3일 경우로 최후에 남았던 서브트리는 그 구성을 전부 알고 있으나 (정확히는 시도해 볼 구성이 2개밖에 없으나) 그 바깥에 있는 정점들에 대해서는 알고 있는 내용이 없다. 이들에 대해 두가지 case가 있다.

  • Case 1. $\{v_1, v_2\} \subset N(v)$. 그렇다면 $v$ 는 $v_1, v_2$ 중 하나와 인접하다. $S_1, S_2$ 중 어느 셋과 인접하지 않은지를 토대로 붙여주면 된다.
  • Case 2. 그렇지 않다. 바깥에 있는 정점들을 뗀 sequence를 우리는 갖고 있으니, 여기에 $S_1, S_2, u, v$ 를 순서대로 추가하자. 루트를 $v$라고 하면, 우리는 리프에서 루트로 bottom-up으로 올라온 정점의 sequence를 알아낼 수 있다. Case 1을 처리했으니 루트에서 $v$로의 거리가 2 이상이다. 고로 부모의 부모가 잘 정의된다. $N(v)$를 보자. $N(v)$의 원소들 중 sequence에서 가장 마지막에 등장하는 것은 부모의 부모이고, 그 다음으로 등장하는 것은 부모이다. 고로, $N(v)$ 를 sequence에서의 등장 순서대로 정렬한 후 뒤에서 두번째 원소를 부모로 지정하면 이 노드의 부모를 알 수 있고, 이 정보로 충분하다.

지금 돌아보면 $\{v_1, v_2\} \subset N(V)$ 인 케이스를 처리 안 해서 WA를 받았던 거 같다. 아무튼 이렇게 하면 다항 시간 알고리즘을 유도할 수 있다. 입력 제한이 크기 때문에 이 알고리즘은 시간 초과를 받는다 (허허...).

마지막으로 필요한 것은 바로 위 연산들을 빠르게 진행하는 것이다. 특히 집합의 동일성에 대해서 여러 가지 연산을 해야 하는데, 이 때 가장 좋은 방법은 Hash를 사용하는 것이라고 생각한다. 랜덤한 64비트 정수 $H_1, H_2, \cdots, H_n$ 을 생성하고, 어떠한 집합의 hash를 이 집합 내부 원소의 $H_i$ 값 XOR로 정의한다. 집합이 같은지를 판별하는 것은 단순 비교로 $O(1)$ 에 가능하다. 삽입 삭제는 단순 비트 연산이다. 이제, 이들 중 중복된 쌍을 찾고, 집합 크기 3인 임의의 원소를 찾는 등의 연산은 dictionary 자료 구조 (set / map)을 많~~~이 만들면 각각 $O(\log N)$ 정도에 가능하다. 시간 복잡도는 $O(M\log N)$ 이다. 정답을 받은 풀이가 아니니, 풀이에 틀린 부분이 있다면 지적을 매우 환영한다. 

(2017.07.05 추가: Chordal Graph의 개념을 안다면 이 문제를 조금 더 쉽게 접근할 수 있다. Tree square 그래프는 Chordal graph이며, 고로 PEO(Perfect Elimination Ordering) 이 존재한다. 또한, 이 PEO는 위에서 리프를 자르면서 얻은 정점 순열과 동일하다. 즉, PEO의 순서가 리프에서 루트로 bottom-up으로 올라가는 순서와 동일하다. 고로, 위와 같이 Hash를 사용하여 복잡하게 순열을 구할 필요가 없고, 단순히 PEO 순서대로 처리해 주면 된다. 지름이 3일 때의 base case를 처리하는 부분을 구현해 주고, 보고한 트리가 올바른 square root인지를 판별하는 루틴을 구현하면 AC를 상대적으로 쉽게 받을 수 있다. 이러한 풀이로는 정답을 받았으며 구현은 이 곳에 있다. Chordal Graph에 대해서는 이 곳에서 ainta의 글을 읽어보는 것을 추천한다.)

H. Simple Polygon (★★★★★)

준비중.