Educational Codeforces Round 184 (Rated for Div. 2) 후기

그동안 많은 일이 있었다. 학교에서 코포 2번을 쳤는데 무려 2솔과 1솔을 해내면서 민트로 회귀해버렸다...

:blobsad:

 

다시 블루로 복귀하고자, 다시는 안 치기로 한 에듀 코포를 치기로 마음먹었다. 그래도 내 첫 코포가 에듀 코포였던만큼, 좋은 결과가 있기를 바랐다.

 

A. Alice and Bob (00:00 ~ 00:09, +1)

간단한 문제다. a보다 큰 값과 작은 값 중 그 개수가 많은 쪽으로 b를 설정하면 된다. 처음에 뻘짓하다가 중복 원소를 체크하지 못해서 1틀한 점이 아쉽다.

 

B. Drifting Away (00:09 ~ 00:15)

무한 루프가 도는 경우만 잘 체크해주고 나머지는 스위핑하면서 세주면 된다. 별로 할 말은 없다.

 

C. Range Operation (00:15 ~ 00:26)

재밌는 문제다. [l, r-1]에서 [l, r]이 될 때 총합이 얼마나 증가하는지 관찰해보면 $2r - A_r$ 라는 놀라운 결과가 나온다. 아마 이걸 떠올린 뒤에는 조금 생각한 뒤에 바로 카데인을 짜러 간 것 같다. 카데인은 그냥 부분 최댓값을 선형으로 구하는 웰노운 알고리즘이다. 이 문제를 풀고 문제가 정말 고능하다고 생각했다. 이렇게 쉬우면서도 재밌는 문제를 내보고 싶다.

 

D1. Removal of a Sequence (Easy Version) (00:26 ~ 00:45)

처음 보자마자 솔직히 아무 생각도 떠오르지 않았다. 처음에는 mod로 접근해야 하나 고민하다가 그건 너무 어렵단 걸 깨달았다. 그러다가 약간 다르게 생각해봤는데, 이 문제를 결정 문제로 치환하면 간단한 이분 탐색으로 해결할 수 있었다! 그러니까 임의의 인덱스 n에 대해서 n 이하에 살아있는 수의 개수를 구하는 건 $O(X)$에 가능하기 때문에, 총 문제는 $O(Xlog10^{12})$에 해결할 수 있었다! 오히려 이 문제가 C보다 쉽다는 의견이 많더라.

 

D2. Removal of a Sequence (Hard Version) (00:45 ~ End)

똥문제

결정 문제를 푸는 함수를 대략 $O(\sqrt{X})$로 만들었다. 같은 step을 한번에 처리하는 방식으로 시간복잡도를 유의미하게 줄일 수 있었다. 하지만, 총 시간복잡도는 $O(10 \log10^{12} \sqrt{X})$로, 안타깝게도 테스트 케이스 개수 때문에 터졌다;;

정해는 놀랍게도 이분탐색을 쓰지 않았다. 어떻게 한 건지는 잘 모르겠지만, 거의 다 풀었다 생각했는데 너무 아까웠다.

 

다행히 블루 복귀에는 성공했다! 퍼플, 그리고 오렌지를 목표로 천천히 달려가야겠다. 업솔빙 꼭 해야지

놀랍게도 퍼플 퍼포다!