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

찍턴 휴가를 나와서 오랜만에 친 대회.

정말 오랜만에 핸디캡 없는 대회이다.

(작년 말의 대회는 부상으로 인해 왼손 하나로 쳤었고, 올해 초의 대회는 군대에서 격리중에 휴대폰으로만 쳤었다. 휴대폰 대회는 후기를 남기지 못하였다.)

---

A: Three Doors

Trivial.

AC: 4 분

---

B: Also Try Minecraft

양방향으로 낙폭 누적합을 전처리해두면 된다.

AC: 12 분

---

C: Recover an RBS

복잡하게 생각을 하다가  꼬였다. Unique한지 아닌지만 판별하면 되므로, greedy한 접근이 가능하다.

?에 치환할 필요한 (와 )의 개수를 계산한 후, 모든 (를 왼쪽으로 몰고 )를 오른쪽으로 몰아 넣는 생각을 해보자. Invalid한 braces가 발생하는 것은 아직 열지 않은 괄호를 닫는 경우이므로, 이렇게 greedy하게 배치하는 것이 최선이다.

Unique한지에 대한 검사는, ((((()()))))에서처럼, (와 )의 접점 부근 두 괄호쌍 위치를 바꿔주면 된다. 이는 greedy한 배치에서 second best이므로, 이 배열이 valid하다면 2개 이상의 배열이 가능하다는 뜻이다.

AC: 1시간 10분

---

D: Rorororobot

$\Delta x$와 $\Delta y$가 $k$의 배수인지 간단히 판별한 후, 이동 경로 사이의 column 중 높이가 너무 높은 장벽이 있는지만 확인하면 된다. Segment tree로 간단하게 처리할 수 있다.

AC: 1시간 31분

 

---

총평

C에서 쓸데없이 많은 시간을 썼다.

퍼포먼스는 무난 그 자체.

 

레이팅 변화: 1809 + 28 = 1837

My Performance: ★★★☆☆

 

---

연습지