대회후기: Educational Codeforces Round 101 (Rated for Div. 2)

2개월만에 참여하는, 종강 후 첫 대회이다.

---

A: Regular Bracket Sequence

A번 문제 치고 문제가 복잡해서 시간을 많이 뺐겼다.

6분에 AC

---

B: Red and Blue

각각의 누적합 최댓값을 더해주면 된다. 이게 왜 11분 걸렸지..?

17분에 AC

---

C: Building a Fence

각 x축 위치마다, fence를 build할 수 있는 구역이 하나의 연속된 구간으로 정해짐이 문제 풀이의 핵심이다. $O(n)$으로 이 구역을 계산해나가면 된다.

43분에 AC

---

D: Ceil Divisions

정말 많은 시간을 투자한 문제다. 대회 종료 후 두명의 친구에게 물어본 결과, 세명이 전부 다 다른 풀이로 해결했었다. $n$과 하나의 숫자만을 남기고 전부 다 $1$로 바꿔놓고, 두 숫자를 남은 횟수 이내에서 $1$ 하나와 $2$ 하나로 만들려고 했었다. 남겨놓을 숫자를 deterministic하게 찾으려고 하다가, 결국 찾지 못하고 세개의 숫자를 남겨놓는 풀이로 넘어갔다. $4, 8, n$을 남겨놓은 후, $n$을 $8$로 여섯 번 나눈 후 $4, 8$을 $1, 2$로 만들면 항상 $n + 5$번만에 처리가 가능하다. 그런데 대회 종료 이후에 친구 풀이를 보니, 두개의 숫자를 남기는 풀이에서 남겨둘 숫자 하나를 deterministic하게 정할 이유가 없었다. $n$ 이외에 남겨놓을 숫자를 $O(n)$으로 탐색하면서 횟수 이내로 들어오는지 검사하는 것이 가능하다... 

1시간 33분에 AC

---

E: A Bit Similar

반쯤 풀고 대회가 종료되었다. 처리해야 하는 문자열들이 하나의 문자열의 substring들이라는 사실에 초점을 두어 생각을 해보다가, 진전이 없어 방향성을 틀었다. 각 substring에 대해, 'bit similar'하지 않은 문자열은 하나씩밖에 없다는 사실까지 발견하고 대회가 끝났다.

 

대회 종료 이후 pasa3232로부터 풀이의 나머지 절반을 들었다. Substring의 개수는 $10^6$개에 불과하므로, bit similar하지 않은 문자열 중 그 integer값이 $10^6$보다 작은 경우만 기록해주면 된다. Bit similar하지 않은 문자열의 집합에 포함되지 않는 문자열 중 integer값이 제일 작은 문자열을 찾는 문제이므로, 이보다 큰 경우는 정답에 영향을 주지 못함을 알 수 있다.

---

총평

오랜만에 한 대회라 살짝 실력이 녹슨 것 같았다. (특히 초반 문제들에서..)

하지만 우려했던 바와는 달리 무난하게 레이팅 방어를 할 수 있었다. 컨디션이 좋았더라면 E를 해결하고 더 큰 폭으로 올랐을수도?

 

레이팅 변화 1917 + 26 = 1943

My Performance: ★★☆☆☆

---

연습지