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

졸리지만 대회 시작.

---

A: Common Subsequence

생략.

4분에 AC

---

B: Sequential Nim

새로운 pile에서 take하는 사람이 주도권이 있다. 현재 pile에서 하나만 남기고 모든 stone을 가져감으로써 다음 pile을 다시 자기 차례에 가져갈 수도 있고, 현재 pile을 전부 다 가져감으로써 상대방한테 다음 pile을 넘길 수도 있다. 단, pile에는 두개 이상의 stone이 있어야 한다. 하나의 stone만 있는 pile의 경우, 무조건 그 하나의 stone을 가져가야 하며 차례는 상대에게 넘어간다.

 

시작 이후 크기 1짜리 pile이 몇개 연속되어 나타나는지를 살펴 그 홀짝성을 바탕으로 판별하면 된다. 단, 오직 크기 1짜리 pile만 있다면 승패 조건이 반대로 뒤집힌다.

12분에 AC

---

C: Prefix Flip (Hard Version)

Easy version과 Hard version이 따로 있지만, 여기서는 하나로 합쳐 설명하겠다.

 

Operation의 대상이 되는 substring은 prefix이므로, 가장 뒤 문자부터 목표값으로 고정시키며 앞으로 점차 진행해야겠다는 생각을 했다. 가장 뒤의 문자를 바꾸려면 문자열 전체에 operation을 해야 하는데, 이때 문자열의 첫 글자가 flip되어 마지막 위치로 들어가게 된다. 만약 이 첫 글자가 목표로 하는 마지막 글자와 다르다면 operation 후 문제 없이 목표값이 들어간다. 만약 같았더라면, 길이 1짜리 prefix에 operation을 한번 함으로써 첫 글자를 flip해주면 된다. 이러한 과정을 뒤에서부터 앞으로 모든 글자에 대해 해준다면 최대 $2n$번의 operation을 하게 된다.

 

Easy version에서는 그냥 flipping을 그대로 구현하였다.

 

Hard version에서는 마지막 위치에 들어가게 되는 문자들이 처음의 문자열에서 어떤 위치에 있었는지에 대한 규칙성을 파악함으로써 복잡도를 낮췄다. 뒤에서 1번째 문자는 앞 1번째, 뒤에서 2번째 문자는 뒤 1번째, 뒤에서 3번째 문자는 앞 2번째, 뒤에서 4번째 문자는 뒤 2번째... 등등 계속 앞뒤 번갈아가며 나아가는 규칙이다. 배열을 계속 뒤집어주는 $O(n)$의 연산이 사라졌으므로 문제를 해결하기에 충분하다.

각각 23, 36분에 AC

---

D: Unmerge

Merge sort에서 사용되는 merge operation을 통해 주어진 permutation을 만들 수 있는지 판별하는 문제이다.

 

오랜 시간을 투자했지만, 방향성을 제대로 잡은 것은 대회 종료 30분쯤 전인 것 같다.

Merge의 대상이 되는 두 배열 $a$와 $b$ 사이를 전환할 수 있는 시점은 permutation 배열을 앞에서부터 살필 때 새로운 최댓값이 등장하는 위치들이다. 이러한 위치들 사이의 간격을 배열에 저장해두고, 이 간격들의 합으로 길이 $n$짜리 source 배열을 만들 수 있는지 확인하면 된다.

 

이 확인과정은 공간복잡도 $O(n)$, 시간복잡도 $O(n^2)$의 DP를 이용하면 된다.

하지만 대회중에 DP가 바로 떠오르지 않았고, 임시로 짜놓은 전탐색 코드가 TLE가 아닌 WA를 뱉어내는 것을 보고 풀이가 잘못된 줄 알고 고민하다가 대회가 끝났다.

WA의 원인은 구현상의 실수였다. (위치들 사이의 간격만 저장해두고, 가장 마지막 위치와 배열 끝 사이의 간격은 고려하지 않았다)

4 WA

---

총평

C2까지 풀었을 때, 전체 17등이었고 레이팅 델타가 +200이었다.

D를 못풀어내서 700등 이상이 떨어졌다.

 

빠르게 출발했지만 D에서 망한 대회. 대회가 끝나고는 엄청 화가 났지만, 돌이켜 생각해보면 내가 대회중에 어떤 실수를 한 것 같지는 않다. D에서 만약 내가 DP를 바로 떠올렸다면 대회 시간 이내에 디버깅을 마쳤을지도 모르겠다. 고로 내 실력의 문제로 생각하겠다.

 

레이팅 변화 1848 + 16 = 1864

My Performance: ★★★☆☆

---

연습지