대회후기: Codeforces Round #606 (Div. 2)

시험기간과 대회가 겹쳐 후기 작성이 다소 늦어지게 되었다.

시험 대비와 대회 참여 사이에서 조금은 고민했으나, 대회 시작 5분 전에 급하게 데스크탑을 켜고 레지스터를 마쳤다.

---

A: Happy Birthday, Polycarp!

주어진 수 \(n\)보다 같거나 작은 자연수 중에서, 숫자 하나의 반복으로 이루어진 수의 개수를 출력하는 문제이다. 빠르게 구현하기 위해, 입력 \(n\)이 들어오면 \(n\)보다 자릿수가 같거나 작은 모든 '동일 숫자 반복으로 이루어진 수'를 \(n\)과 크기 비교하였다. 시간복잡도는 \(O(\log n)\)이다.

4분에 AC

---

B: Make Them Odd

자연수의 배열이 들어올 때, 모두 홀수로 만들고자 한다. 홀수로 만들기 위한 연산은 특정 숫자를 골라 모든 occurrence들을 절반으로 나누는 것이다. 이때 필요한 연산의 최소 횟수를 구하면 된다. 연산의 횟수를 최소화하기 위해서는 나누는 과정에서 동일한 숫자를 거쳐가는 수들을 적절히 처리해 주어야 한다. 한단계 더 생각해보면 이렇게 동일한 숫자를 거쳐가는 숫자들은 최종적으로 같은 홀수가 됨을 알 수 있다. 따라서 주어진 배열의 모든 수를 홀수가 될 때까지 2로 반복해 나누고, 같은 홀수가 여러개라면 그중 나누기 2를 제일 많이 필요로 했던 횟수만큼만 최종 카운트에 세주면 된다. 그보다 나누기 횟수가 덜 필요한 수들은 자연스럽게 함께 홀수가 되기 때문이다.

10분에 AC

---

C: As Simple as One and Two

주어진 문자열에서 'one'과 'two'의 모든 occurrence를 제거하기 위해 문자들을 삭제한다. 이때 삭제해야 하는 문자의 수를 최소화해야 한다. 처음에는 'one'과 'two'의 겹치는 문자가 'o' 하나뿐임에 착안해 'one'과 'two'를 구성하고 있는 모든 'o'를 삭제하는 솔루션을 제출하였다. 하지만 이때 간과하고 있었던 것은 'oone'과 같이 'o'가 연속해 등장하는 상황에서는 다른 문자를 제거하는 것이 더 최적의 풀이가 된다는 사실이다. 해결은 간단했다. 'o'가 연속하지 않으면 'o'를 원래대로 제거하고, 'o'를 제거해도 'o'가 하나 더 옆에 있는 상황이라면, 나머지 문자 중에서 제거한다.

2 WA 후 36분에 AC

---

D: Let's Play the Words?

이진문자열 끝말잇기 문제이다. 주어진 문자열들을 전부 사용해 끝말잇기 형식으로 늘어놓고자 하는데, 주어진 단어들로 끝말잇기가 불가능하다면 특정 단어들을 뒤집을 수가 있다. 뒤집는 단어의 수를 최소화해 끝말잇기가 가능하도록 해야 한다. 단, 추가로 주어진 조건 하나는 모든 단어들이 뒤집은 후에도 unique해야 한다는 점이다. (모든 단어는 unique하게 주어진다.)

 

문제 풀이는 단계적으로 접근했다. 먼저 뒤집어도 의미가 없는 단어들(i.e. 시작과 끝이 같은 단어)과 뒤집으면 unique하지 않은 단어들을 제외시켰다. 남은 단어들이 뒤집을 수 있는 단어들이다. 단어들은 시작과 끝만 중요하기에 00, 11, 01, 10의 꼴로 나눌 수 있는데, 00과 11의 꼴은 01과 10꼴이 하나라도 있으면 그 사이에 적절히 배치하는 것이 항상 가능하기에 문제의 해결을 위해서는 01과 10꼴에 초점을 맞춰야 한다. 끝말잇기가 가능하려면, 01꼴과 10꼴의 개수 차이가 1 이하이어야 함을 알 수 있다. 따라서 주어진 단어들을 보고 01꼴과 10꼴의 개수 차이를 확인한다. 앞서 확인한 뒤집을 수 있는 단어들을 적절히 뒤집어준다면 두 꼴의 개수 차이를 1 이하로 내릴 수 있다. (뒤집을 수 없는 단어 중 01꼴과 10꼴의 개수는 필연적으로 같기 때문에 뒤집을 수 있는 단어 중에서만 고려해주면 된다.) 이렇게 문제를 해결하고 제출하였다.

1시간 4분, WA

01꼴과 10꼴이 전혀 없으면 끝말잇기가 불가능하다고 판정했었는데, 00꼴과 11꼴 둘 중 한 종류만 존재하면 괜찮았다. 빠르게 수정 완료.

1시간 6분, AC

---

E: Two Fairs

주어진 simple connected graph의 두 node A와 B가 정해진다. 이때 A와 B가 아닌 두 node X, Y를 정했을 때, X에서 Y로 가기 위해서 A와 B를 필수적으로 경유해야 하는 경우가 있다. 문제는 이러한 X, Y의 조합의 개수를 묻는다.

 

문제를 처음 보고서는 아무 생각이 들지 않았다. 솔직히 해결할 수 있으리라 생각하지 않아 별다른 노력을 하고 있지 않기도 했다. 하지만 대회 종료 30분을 앞두고 해결을 위한 실마리가 떠올랐다. 만약 A와 B를 필수적으로 지나야만 하는 두 도시 X, Y가 존재한다면, 그래프의 모든 node를 1. A에만 연결된 구역 (X가 포함된 구역), 2. A와 B 사이의 구역, 그리고 3. B에만 연결된 구역 (Y가 포함된 구역)으로 나눌 수 있지 않을까?

 

이 생각을 갖고 문제를 보니 풀이 방법이 보이기 시작했다. 앞에서와 같이 그래프 전체를 세 구역으로 나눈다면, A에만 연결된 구역의 node의 수과 B에만 연결된 구역의 node의 수를 곱해주면 답이 되는 것이었다(i.e. the ways of selecting X and Y). 세 구역의 분류를 위해 DFS를 하며 세가지 색깔로 node를 칠해 나갔다. 만약 탐색 중 A 혹은 B를 맞닥뜨리면 terminal node로 취급해 그 구역의 탐색을 중단하였다. 만약 그래프가 위와 같이 세 구역으로 나누어질 수 있다면 정답은 0보다 클 것이고, 세가지 색으로 칠해져 있을 것이다. 총 색이 세가지이므로, 두번의 탐색을 통해 두 색깔만 칠해놓으면 해결이 가능하겠지... 라고 생각하며 제출하였다.

1시간 48분에 WA

구현이 틀렸나? 디버깅 후 다시 제출.

1시간 57분에 WA

 

대회 종료 후 몇시간이 지나서야 문제를 발견하였다. A 혹은 B와 마주치면 바로 탐색을 종료하는 것이 문제였다. A에만 연결된 가지가 여럿이 있을 수 있는데, 기존의 구현에서는 이 모든 가지를 각각 다른 색으로 칠하고 있었다. 모든 node가 visited일 때까지 탐색을 필요한 만큼 새로 시작하며, A, B와 인접해 있는지의 여부를 기준으로 node 개수를 counting하도록 수정하였다. AC 판정이 나왔다.

---

총평

바로 드는 생각은 아쉬움이다. 조금만 더 정확하게 생각했더라면 E를 해결하지 않았을까?

아쉬움에도 불구하고 이번 대회는 매우 좋은 성적을 거뒀다. 사실 레이팅 상승폭이 역대 최대이다.

깔끔한 문제들이 나와서 별다른 어려움 없이 문제 해결을 위한 생각에만 집중할 수 있었던 것 같다.

큰 실수 없이 좋은 performance를 보인 대회로서 만족한다.

 

레이팅 1700점대 회복!

 

레이팅 변화 1630 + 77 = 1707

My Performance: ★★★★☆