대회후기: Codeforces Global Round 9

지난 대회가 끝나자마자 레지스터했던 대회이다.

그때 레지스터해두지 않았다면 귀찮아서 하지 않았을 것 같다.

---

A: Sign Flipping

문제 착각해서 뻘짓하다가 정신 차리고 홀짝성에 맞춰서 부호 부여.

5분에 AC

---

B: Neighbor Grid

그냥 꽉꽉 채워주면 된다. 네 귀퉁이는 2, 네 모서리는 3, 나머지 값들은 4로 만들어 줄 수 있는지만 확인하면 된다.

 

근데 이 간단한걸 잘못 짜서 디버깅하면서 시간 다 버렸다.

4 WA 후 26분에 AC

---

C: Element Extermination

지난 대회의 문제가 떠오르면서 이 문제 또한 greedy일 것이라는 느낌을 받았다.

 

삽질을 엄청 했다.

 

처음에는, 자료를 deque에 넣어 양 끝에서 greedy하게 두개씩 pop하고, 왼쪽 끝에서는 둘 중에 작은 값을, 오른쪽에서는 큰 값을 다시 넣어 전부 다 처리 가능한지 판별하는 코드를 제출했다.

++WA;

 

다음에는, 문제를 처음 봤을 때 받았던 느낌을 따라 제일 큰 값을 기준으로 생각해보기로 했다. 배열에서 제일 큰 값을 기준으로 본다면, 그 값의 왼쪽에 있는 모든 값들은 처리가 가능하다. 제일 큰 값과 그 왼쪽에 있는 값들을 다 쓸어버리면 결국 제일 왼쪽에 있던 값이 남게 된다. 그런데 또 혼자 착각해서 왼쪽에 있던 값들 중 최솟값이 남는다고 생각했다. 이런 방식으로 계속 제일 큰 값을 찾아주고, 그 왼쪽 값들을 치워주는 과정을 반복해서 모든 값을 치울 수 있는지 확인하면 된다. 물론 착각때문에 틀렸다.

++WA;

 

(거의) 마지막으로는, 앞에서 한 착각을 깨닫고 수정하였다. 그런데 수정 과정에서 필요한 코드를 필요 없는 코드인 줄 알고 지워버렸다.

++WA;

 

(정말) 마지막으로는, 모든 수정을 마치고 제출하였다. 진짜 이 풀이마저 실패하면 대회 포기했을 수도 있을 것 같다.

5 WA 이후 1시간 20분에 AC

UPD) 조금 더 생각해 본다면 배열의 시작과 끝 원소만 비교하면 된다는 것을 알 수 있다.

엌 ㅋㅋㅋ 난 뭘 한걸까 ㅎㅎ

---

D: Replace by MEX

문제 중간쯤에 적혀있는 말이 의미심장했다:

It's worth mentioning that the MEX of an array of length $n$ is always between $0$ and $n$ inclusive.

 

음... 그냥 MEX값을 계속 그 값에 해당하는 index에 넣으면 되는 것 아닌가? 라는 생각이 바로 들었다.

결론은 이게 맞다.

 

다만 MEX값이 $n$으로 나오는 경우, 즉 모든 필요한 값들이 이미 있지만 순서가 바르지 않은 경우가 문제가 된다.

이런 경우는, 그냥 제 자리에 있지 않은 값들 중 제일 앞에 있는 값을 $n$으로 바꾸어주었다. (꼭 제일 앞 값은 아니어도 될 것 같다.)

 

이미 제 자리에 값이 들어가 있다면, 이 값은 정의에 의해 다시 MEX값이 될 수 없다.

고로 비둘기집의 원리 비슷한 느낌으로, $2n$번 MEX값을 자기 index에 넣는 과정을 반복한다면 모든 MEX값이 한번씩 나올 것 같았다. 최종적으로 필요 없는 값인 $n$이 계속 나와봤자 두번 중 한번씩만 나올 것이다.

1시간 40분에 AC -> RTE

UPD) break condition 부실하게 짜서 RTE 받았다. 덕분에 100점 이상 떨어지게 생겼다.

---

E: Inversion SwapSort

음... 문제가 재밌군 ㅎㅎ

---

총평

뻘짓이고 삽질이고 구현 미스고 제발 좀 그만하자...

레이팅 오를 대회가 레이팅 내려가는 대회로 바뀌어버린다.

 

레이팅 변화 1947 - 99 = 1848

My Performance: ★☆☆☆☆

---

연습지