ICPC Yokohama Regional 2018

오랜만에 셋을 돌았다. rkm0959와 2인 팀으로 돌았다. 문제들이 대체적으로 마음에 들었지만, 그냥 마음이 아프다. 업솔빙한 문제들의 풀이를 간략하게 정리해 본다.

A Digits Are Not Just Characters

더러운 문제다. 생략.

B Arithmetic Progressions

보자마자 "아 ㅋ 10초 컷이네 ㅋ" 생각해서 키보드를 잡자마자 그 풀이가 $O(N^3)$임을 깨달았다. 20초 더 생각하니 $O(N^2)$더라. 내 앞에 있던 놈도 그런 거 같았다.

$a_1$과 $a_2$로 쓸 두 개의 수를 정하면 만들 등차수열이 정해지고, 등차수열이 정해졌다면, 주어진 수열에서 등차수열을 몇 번째까지 뽑을 수 있는가는 쉬운 연습문제이다. 이를 단순히 구현하면 $O(N^3)$이다. 여기서, DP처럼 같은 $(a_1, a_2 )$의 쌍을 한 번만 세도록 처리해주자. 이 부분을 잘 이해하기 힘들다면, DP같이 처리한다고 생각하자. $dp(i, j)$를, $a_1 = v_i$, $a_2 = v_j$로 두었을 때 만들 수 있는 등차수열의 길이로 두자. $v_k = a_3 = a_2 + (a_2 - a_1)$이 되는 $k$가 존재한다면 $dp(i, j) = 1 + dp(j, k)$가 된다. 이제, 중복된 $(i, j)$에 대해 한 번만 셀 수 있으며, $O(N^2)$의 시간 복잡도에 문제를 해결할 수 있다.

C Emergency Evacuation

다른 사람의 방해가 없을 때, 각 사람이 출입문까지 도달하는 최소 시간(i.e. 거리)는 쉽게 알 수 있다. $t_i = |W-x_i| + |H-y_i| + 2$일 것이다. 그냥, 각 사람이 그 시점에 출입문 앞에 뿅 하고 나타나서 줄을 선다고 생각하자. 그리고는 1초에 한 명씩만 내보내준다고 생각하자. 이 경우, 문제의 풀이는 자명하다. $t_1 , ..., t_N$을 오름차순으로 정렬하고, 각 $i=2,...,N$에 대해 $t_i = \max (t_{i-1}+1, t_i)$를 수행하면 된다. 이 때 마지막 사람은 연산이 끝난 후 $t_N$의 시간에 나가게 될 것이다.

그렇지만, 원래 문제에서는 제약사항이 좀 더 많았으니 답이 좀 더 크지 않을까? 사실은, 원래 문제의 답도 같다! 이 사실은, 거꾸로 사람들을 들여보내주는 상황을 생각하면 쉽게 납득이 된다. 사람들을 출입문에서 1초에 한 명씩 차례대로 들여보내야 하는 상황이라면, 가장 자리가 멀리 있는 사람부터 들여보내야 모두가 앉게 되는 시간이 빨라진다.

D Shortest Common Non-Subsequence

LCS 문제와 비슷해 보인다. 풀이도 LCS와 비슷할 것처럼 생겼다. $dp[i][j]$를, $A[i...]$과 $B[j...]$의 Shortest common non-subsequence의 길이라고 하자. 종이에 조금 끄적여보면 그럴듯한 점화식이 나온다. $zero_S (i)$를, $S[i...]$에 등장하는 첫 $0$의 위치로, $one_S(i)$를 $S[i...]$에 등장하는 첫 $1$의 위치로 두자. 그러면,

 

$dp[i][j] = min(dp[zero_A(i)+1][zero_B(j)+1], dp[one_A(i)+1][one_B(j)+1])$

 

이 된다. 유의. 만약 입력으로 빈 문자열 두 개가 들어온다면 답은 길이 1인 문자열 $0$이다. 그러니, (0-indexed notation으로) $dp[N][M] \neq 0$이고, 오히려 $dp[N+1][M+1] = 0$이다. $A[N+1...]$라는 말은, 빈 문자열과는 뉘앙스가 다른, "길이가 -1인 문자열"이며, $A[N...]$과는 오히려 구분해야 하는 것이다. 이 점을 "세심하게" 고려해서 세심한 DP식을 세워야 한다. 나는 이 문제를 풀면서 불길한 예감을 느끼면서도, 이 진실을 외면하고 사전순 최소로 복원해야 한다는 조건 탓을 했다. 고통스럽더라도 진실을 마주할 수 있는 용기가 필요하다.

E Eulerian Flight Tour

왜 맞지?

*

F Fair Chocolate-Cutting

*

G What Goes Up Must Come Down

수열에서 가장 작은 수는 가장 왼쪽 또는 가장 오른쪽으로 (언젠가는) 보내야 한다. 그리고, 그렇게 최소원소를 양쪽 끝 중 하나로 보내면, 남은 수열에 대한 문제는 완전히 독립적인 다른 문제이다. 그러면, 가장 작은 수를 왼쪽으로 보내야 할까, 오른쪽으로 보내야 할까? 그냥 가까운 쪽으로 보내면 장땡이다. 어느 쪽으로 보냈든 이후의 문제와는 별 상관이 없으니.

구현할 때에는 우선순위 큐, 펜윅 트리, 세그먼트 트리 등을 쓰면 된다.

H Four-Coloring

구사과님의 오색 정리 포스트를 참조한다. 이 글에서 오색 정리의 첫번째 증명을 간략히 리뷰한다:

 

• 수학적 귀납법을 사용한다. 기저는 물론 참이다.
• 증명은 무방향 평면 그래프에는 차수가 5 이하인 정점이 존재한다는 보조정리에서 시작한다. 이건 오일러 방정식에 의해 유도되고, 그냥 믿자, 지금은.
• 그러한 정점 $v$를 하나 고르고, 그래프에서 $v$를 제외한 정점들을 모두 칠해본다. 귀납 가정에 의해 물론 가능하다.
• $v$의 최대 다섯개인 이웃을 $u_1, \cdots, u_5$로 각도 순서대로 이름붙이자. 이 이웃들은 어떻게든 칠해져 있을 것이다.
• 이웃들을 칠할 때 1번 색에서 5번 색까지를 모두 사용하지 않았다면 운이 좋은 것이다. 이웃들을 칠할 때 사용하지 않았던 색 하나를 칠하면 된다.
• 운이 나쁘게 이웃들에게 쓰고 남은 색이 없다면 어떻게 할까? 그래도 괜찮다. 이웃들의 색을 적절히 재배치해서 여유분을 하나 남길 수 있다.
• $u_1, \cdots, u_5$에 칠한 색을 차례로 $c_1, \cdots, c_5$라고 하자. 원래 그래프에서 $c_1, c_3$의 색으로 칠한 정점만을 남겼을 때, $u_1$과 $u_3$이 연결되어 있지 않다면, 그래도 운이 좋은 편이다. $u_1$의 색을 $c_3$으로 바꾸고, $u_1$ 주변에 있는 $c_3$으로 칠해진 정점들의 색을 $c_1$으로 바꾸고, 그 주변의 정점들의 색을 $c_3$으로 바꾸고, 쭉 해 준다. $u_1$과 $u_3$이 연결되지 않은 경우이므로 이 과정은 적당히 굴러가다 끝난다.
• 위 과정이 끝나면 $u_1$의 색이 $c_3$이 되면서도 올바르게 색을 칠하게 되었고, 그러면 $v$에는 $c_1$을 칠할 수 있게 되었다! 예~!
• 정말 운이 나쁘다면..? ㅜㅜ 그러면 어쩔 수 없다. 대신, $u_2$와 $u_4$를 붙잡고 같은 짓을 해 보자.
• 증명의 핵심은, 두 과정이 모두 실패할 수는 없다는 것이다. 즉, $c_2, c_4$의 색으로 칠한 정점만을 남겼을 때, $u_2$와 $u_4$는 무조건 분리되어 있다는 것이다!
• 왜? 그래프가 평면 그래프이기 때문이다! 두 과정이 모두 실패했다면, $c_1$, $c_3$으로 칠해진 정점으로 $u_1$과 $u_3$을 이은 경로와, $c_2, c_4$로 칠해진 정점으로 $u_2$와 $u_4$를 이은 경로가 모두 존재한다. 그런데, 두 경로는 교차한다! 그러면 그 교차점은 $c_1, c_3$ 중 하나로 칠해져야 하는 것인가, 아니면 $c_2, c_4$ 중 하나로 칠해져야 하는 것인가? 여기서 두 과정이 모두 실패하면 모순이고, 두 과정 중 하나는 성공함을 보였다.

위 증명은 실제적으로 일반적인 평면 그래프를 오색으로 색칠하는 방법을 제시한다. 그런데, 문제에서 제시하는 평면 그래프는 더 강력한 성질을 가진다. 얘는 무조건 차수가 4 이하인 정점을 하나 가진다. 바로 그래프의 가장 오른쪽 아래에 있는 점이다. 얘를 가지고 위의 과정을 그대로 따라가면 입력으로 주어지는 형태의 그래프를 4개의 색으로 칠할 수 있다!!!(증명의 마지막 부분에서 $u_5$는 전혀 써먹지 않았다는 점을 확인하라.) 시간 복잡도는 $O(N^2)$로 별 문제없다.

I Ranks

*

J Colorful Tree

색안경을 끼고 $c$번 색의 관점에서만 문제를 보자. 사실 이 문제는 다음 세 가지 연산을 처리하는 문제와 같다.

 

1. 정점 $v$에 표시를 한다.
2. 정점 $v$에 한 표시를 지운다.
3. 표시한 정점들을 모두 잇기 위해 필요한 최소 간선 수를 구한다.

3번 질의의 답은, 초기에는 0이고, 1번과 2번 질의에 따라 증가하거나 감소할 것이다. 3번 질의의 답을 질의가 들어올 때 계산하지 않고 1번과 2번 질의가 들어올 때 변화량을 잘 계산해줘서 슝슝 더하고 빼 줄 수 있지 않을까?

트리를 루트에 매달고, 가만히 생각해 보자. 만약 지금 매달아놓은 트리의 정점 몇 개에 표시가 되어 있다고 생각해 보자. 이들을 모두 잇는 간선들은 또 다른 트리처럼 생겼을 것이다. 얼핏 보면, 이들 전체의 LCA ($l$이라 두자) 에다가 표시한 정점들을 주렁주렁 매달아둔 것처럼 생겼다. 즉, 이들을 모두 잇는 간선들은 LCA에서 각 정점으로 가는 경로들의 합집합이다. 이제, 여기에 새로운 정점 $x$를 추가하면 3번 질의의 답은 얼마나 증가할까?

만약 새로 추가한 정점 $x$가 $l$의 자손이 아니라면, 정확히 $x$와 $l$ 사이의 거리만큼 답이 증가한다. 만약... $l$의 자손이라면? 고른 정점들을 모두 잇기 위해서는 $x$에서 $l$로 가는 경로만큼을 결국은 추가해야 할 건데, 기존에 골라둔 간선들과 얼마나 겹치는지를 우리는 모른다. $x$에서 가장 가까운 '가지'를 찾아서, 그 가지까지의 거리를 재야겠다. 그러기 위해서 우리는 정점들에 DFS 순서를 매겨두고, 고른 정점들 중에서 $x$와 DFS 순서가 가까운 두 정점(왼쪽에서 하나, 오른쪽에서 하나)만 잡아서 실제 거리를 재보면 된다. 그 중 짧은 길이만큼을 3번 질의의 답에 더해준다.

삭제는 반대로 하면 된다. (진짜로!)

K Sixth Sense

편의상, 상대편이 가진 배열을 $a$, 내가 가진 배열을 $b$라고 하자. 사전순으로 최대인 배치를 출력하라는 조건이 없을 때에는 잘 알려진 그리디 알고리즘으로 풀 수 있다.

 

1. $a$와 $b$를 정렬한다.
2. $a$의 원소를 $a[1], ..., a[N]$ 순서대로 보면서, $b$에 $a[i]$보다 큰 원소가 존재하면 사용해서 점수를 올린다.

(물론, $a$를 정렬하지 않아도 문제없다.)
이 방법은 $O(N)$이다.

사전순으로 최대인 배치를 출력해야 하는 게 좀 짜증난다. 첫번째 판에는 뭘 내야 할까? 첫번째 판에서 이길 수 있으면 언제나 이기는 게 이득이다. 사전순 최대를 고려하지 않는다면 $a[1]$ 초과의 첫번째 수를 쓰는 게 이득인데, 이제 좀 애매해진다. "첫번째 수로 얘를 써도 여전히 최적해가 되는지"로 parametric search를 돌리자. 첫번째 수 후보를 $\log N$번 고려하게 되므로, $O(N \log N)$에 첫번째 원소를 결정할 수 있다. 물론, 전체 시간 복잡도는 $O(N^2 \log N)$.