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

이런 저런 일정으로 대회 참여를 못하다가, 오랜만에 복귀하게 되었다.

컨디션이 좋지 않아 평소보다는 못한 것 같지만, 레이팅 방어는 성공하였다.

---

A: Sweet Problem

이번 대회에서 체감상 제일 어려웠던 문제다. 문제 description은 매우 간단한데, 최적의 solution을 찾는 방법을 떠올리지 못해 한참을 헤맸다. 결국 직관적으로 풀었는데, 방법이 맞았던 모양이다.

23분에 AC

---

B: PIN Codes

최대 10개의 PIN code들을 서로 다른 code로 만들기 위한 최소 수정 횟수와 그 수정 결과를 출력하는 문제였다. 거의 문제를 보자마자 마지막 자릿수만 처리한다면 풀 수 있음을 알 수 있었다. 구현하는 것에 시간이 조금 소요되었다.

49분에 AC

---

C: Everyone is a Winner!

예전에 풀어보았던 UCPC 기출이 바로 떠오르면서, 비슷한 느낌으로 쉽게 풀 수 있었다. 특정 숫자 \(n\)을 그 숫자보다 작은 모든 자연수 \(i\)로 나누었을 때의 몫을 알아야 하는 문제이다. 모든 \(i\)에 대해 계산하는 대신, \(\sqrt n\)까지의 \(i\)만 살펴보아도 나머지는 대칭성을 이용해 해결할 수 있다.

1시간 6분에 AC

 

---

D: Secret Passwords

보자마자 지난 대회에서 내가 D번을 풀지 못했던 이유인 union-find가 떠올랐다. 동일한 알파벳을 하나라도 갖고 있는 두 password는 같이 묶인다. 이런식으로 password들을 묶어나갈 때, 묶음의 개수를 출력해야 한다. 아직 union-find를 공부하지 않은 상태였는데, 이번에도 공부를 안해 못푸는것인가... 싶었을 때 알파벳을 기준으로 생각하면 문제를 풀 수 있겠다는 생각이 들었다. 알파벳의 수가 26개밖에 되지 않으므로 그냥 dictionary에 동시에 등장하는 알파벳들을 묶은 후, 알파벳 묶음의 개수를 세면 되는 것이었다.

1시간 16분에 AC

---

E: Editor

너무 피곤해서 문제만 읽어보고 컴퓨터를 종료했다. 커서 이동과 parentheses 입력이 존재하는 어떤 editor의 명령 입력이 주어졌을 때, 각 입력 이후에 존재하는 string의 parentheses가 valid한지 확인함과 동시에 parentheses의 최대 nesting이 몇 단계인지를 알아야 하는 문제이다. Stack을 잘 이용하면 풀릴 것 같다는 생각이 들었다. 앞서 말했듯이 풀이를 시도하지는 않았다.

이후에 들은 바에 의하면 segment tree와 lazy propagation을 이용한 풀이가 있다고 한다.

---

총평

매우 피곤하여 눈을 뜨고 있기도 힘들었던 것을 감안한다면 준수한 성적이라고 생각한다.

그냥 무난한 방어였다.

 

레이팅 변화 1614 + 16 = 1630

My Performance: ★★★☆☆