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

오르긴 하지만 살짝 아쉬운 대회이다.

---

A: Puzzle From the Future

요즘 코포가 어렵다. 내가 알던 A가 아니다 ㅋㅋㅋㅋㅋ

자릿수가 줄어들면 안되고, 높은 자리수가 큰 숫자가 장땡이니 greedy하게 짜면 된다.

AC: 5분

---

B: Different Divisors

문제가 신박해서 잠시 어... 이건 뭘까... 하고 있다가 바로 직관적인 greedy 풀이가 떠올랐다. $pq$ 형태로 소수 두개가 곱해진 형태의 수를 찾는데, $p$는 $1 + d$ 이상인 숫자부터, $q$는 $p + d$ 이상인 숫자부터 찾으면 된다. 엄밀한 증명은 사실 안해봤다. (대회에서는 직관이 최고다)

AC: 12분

---

C: Array Destruction

구현에서 자꾸 꼬여서 풀기까지 오래걸린... 것도 맞지만, 구현 과정에서 계속 반례를 찾아내면서 제대로 된 풀이로 코드가 수렴하였다. $x$ 값은 감소할 수밖에 없기 때문에, 제일 큰 값은 첫번째로 제거되는 pair에 포함되어야 한다. 결국 돌고 돌아 도달한 풀이는, 이 제일 큰 값과 같이 제거할 값 $n$ 가지를 다 해보는 것이다. 각 경우를 simulate하는 것은 $O(n)$에 가능하다. 고로 $O(n^2)$ 풀이가 되는데, 구현을 위해서는 임의의 원소 삭제와 제일 큰 원소를 빠르게 찾을 수 있는 자료구조가 필요하다. C++에서는 multiset이 이런 자료구조인데, Python으로 짜느라 list와 dictionary를 혼합시켜 구현하느라 살짝 읭 이게 맞나? 싶었었다.

AC: 48분

---

D: Cleaning

풀이를 구상하기 위한 모든 분석을 마친 상태였지만 결국 풀이까지 도달하지 못했다.

 

배열의 첫 원소는 두번째 원소와만 함께 지울 수 있다. 고로 첫 원소가 전부 없어질 때까지 두번째와 함께 감소시키고, 남은 두번째를 세번째와 감소시키고... 이러한 과정을 마지막 원소까지 반복하는 동안, 1. 없애야 하는 왼쪽 값보다 오른쪽 값이 작아지지 않고, 2. 모든 작업 이후에 값이 남지만 않으면 성공이다.

 

대회 중에 떠오르긴 했지만 크게 신경쓰지 않았던 성질은, 배열의 성질이 좌우 대칭인지라 위의 제거법을 마지막 원소에서부터 시작하여도 동일하다는 것이다. 이 성질에 집중하면, 자리를 바꾸는 각 경우마다 $O(1)$ 복잡도로 성공 여부를 확인할 수 있다. 앞으로부터 원소를 제거해가는 과정을 저장한 배열과, 뒤에서부터 원소를 제거해가는 과정을 저장한 배열을 각각 계산해두면, 바꿔친 값들과 인접한 위치의 원소까지 포함하여 총 4개의 값만 참고해 성공 여부를 계산할 수 있게 된다. 즉, 각 바꿔치는 경우마다, 바꿔친 위치의 앞과 뒤쪽 원소들을 제거하는 방법이 이미 결정되어 있다는 것이다.

 

대회 시간중에는 이와는 방향성이 많이 다른 풀이를 시도하고 있었다(아래 연습지에서 볼 수 있다 ㅋㅋㅋ). 이 문제를 맞혔다면 더 많이 오를 수 있었는데 아쉬움이 있다.

---

총평

솔직히 D 정도는 풀어줬어야 한다고 생각한다. 

 

레이팅 변화: 1781 + 80 = 1861

My Performance: ★★★☆☆

---

연습지