Codeforces Round #659 (Div. 2)

난이도가 좀 괴상하다. B1+B2 푼 사람보다 C푼 사람이 더 많다.

꾸역꾸역 B2를 밀었더니 Codeforces Anytime에서 오렌지 퍼포먼스가 떴다 ㅋㅋ

 

A. Common Prefixes

인접한 두 문자열의 공통 prefix의 갯수가 주어질 때, 만족하는 문자열의 배열을 출력하는 문제. 각 문자열의 한 문자에 대해서 생각해보면, 서로 같은지 다른지만 중요하는 것을 알 수 있다. 따라서 모든 문자를 a와 b로 통일해보자. prefix 갯수만큼은 그대로 두고, 그 이후는 이전 문자열과 다르게 선택하면 된다. 문자열의 길이에 대한 조건이 있는데, 이미 조건을 만족했으므로 그냥 최대 길이인 200개로 꽉 채워서 만들어도 된다.

 

B2. Koa and the Beach

시간에 따른 파도를 { k, k-1, k-2, ... , 2, 1, 0, 1, 2, ... , k-2, k-1, k } 로 변환해보자. 그러면 각 위치에서 존재할 수 있는 시간이 구간으로 나타나게 된다. 시간이 지남에 따라 현재 높이를 잘 관리하면, 현재 높이가 구간 안에 들어가 있는지 확인해줄 수 있다. 만약 모든 구간이 가능한 경우 즉, 시간과 무관하게 항상 가능한 위치가 있다면 원하는 높이로 이동할 수 있다.
현재 높이가 구간 왼쪽에 있다면, 조금 더 기다려서 높이가 낮아지기를 기다릴 수 있다. 반대로 구간 오른쪽에 있다면 더 이상 진행할 수도 없고 기다릴 수도 없기 때문에 실패한다. 이 과정을 시뮬레이션하면 O(n)안에 해결이 가능하므로, 두 문제 모두 해결이 가능하다.

딱봐도 더러워보이는 문제다. 버추얼이라 그냥 망할 각오하고 구현했더니 다행히 맞았다. 레이티드였으면 나도 C로 도망갔을 것 같다.

 

C. String Transformation 1

제일 먼저, 더 작은 문자로는 변경할 수 없으므로 모든 문자를 순회하면서 예외처리해준다.
각 문자를 변경하는 과정을 그래프로 모델링해보자. 어떤 문자 X를 Y로 바꾸는 것을 정점 X에서 Y로의 간선으로 표현할 수 있다. 잘 관찰해보면 간선의 방향이 더 큰 문자 방향으로만 생기므로, 이 그래프는 DAG임을 알 수 있다. 즉, DAG에서 최소 갯수의 간선을 사용해서 모든 정점을 지나는 방법에 대한 문제가 된다. 그래프에서 모든 정점이 연결되면서 간선의 갯수가 최소인 경우는 spanning tree임이 자명하다. 트리의 간선의 갯수는 (연결된 정점의 갯수)-1 이므로 union-find 등으로 그래프의 연결 상태를 세어주고 간선의 갯수를 계산하면 된다. 그래프들이 서로 연결되지 않을 수도 있음에 주의하여, 각 컴포넌트끼리 따로 계산해준다.

약간 짬밥?으로 풀었다. 아이디어가 없어서 말린 문제들 중에 그래프로 모델링하는 풀이가 많았어서, 뭔가 상태 전이가 있는데 아이디어가 전혀 떠오르지 않으면 그래프로 한번 모델링해보는 경향이 있다. 모델링해보니까 금방 규칙이 보였다.