Educational Codeforces Round 116 (Rated for Div. 2)

지난 Div.1의 여파 이후 이틀을 쉬고 버츄얼을 다시 돌았다.

A. AB Balance (0:07, +) *900

A치고 좀 어려웠던 것 같다. 뭔가 복잡한 풀이가 떠올랐는데, 아닌 것 같아서 좀더 생각해 보니 첫 글자와 마지막 글자가 같기만 하면 된다는 사실을 알 수 있었다.

 

B. Update Files (0:13, +1) *1100

현재 파일 수가 \(k\)보다 적으면 계속 2배가 되고, 아니라면 \(k\)씩 더해진다. 앞은 반복문으로 대충 처리하고, 뒤는 나눗셈으로 횟수를 구해주면 된다. 그냥 무지성 반복문을 썼다가 TLE를 한 번 받아버렸다.

 

C. Banknotes (0:25, +) *1400

대충 어떻게 하면 될 지는 보이는데, 구현이 귀찮다. 앞부터 그리디하게 처리해주면 된다. 개수는 뒤 동전과의 액수 차이를 이용하자. 자세한 설명은 생략하겠다.

 

D. Red-Blue Matrix (1:53, +) *2400

처음 봤을때 뭔가 바로 생각이 안 났고, E가 많이 풀렸길래 도망갔다 다시 잡았다. \(k\)를 옮겨가며 처리해주자. 우선 왼쪽을 먼저 봤을 때, 색을 구분하려면 잘 나누어지는 경계를 찾아야 한다. 이는 각 행의 왼쪽 부분에서 최솟값, 최댓값을 구간으로 표현했을 때 빈 부분을 말한다. 이는 set 등으로 각 행의 왼쪽/오른쪽 최소/최댓값을 관리해주고 pair를 정렬하면 찾을 수 있다. 이러한 상황은 최대 \(O(NM)\)번 발생하기 때문에, 이 때마다 오른쪽 역시 잘 나누어지는지 빠른 시간 안에 체크할 수 있다면 문제를 해결할 수 있다. 이 역시 비슷한 아이디어로 set을 관리해주면 해결할 수 있다. 왼쪽에서 정한 색에 따라 오른쪽이 잘 나누어지는지 같은 방법으로 판단하고, set 역시 잘 관리해주자. 막 어렵진 않은데 스위핑에 익숙해야 하고 할 게 좀 많아서 까다로웠던 것 같다.

 

E. Divide Square (1:14, +) *2100

\(N\)이 500이므로 \(O(N^3)\) DP를 시도해보자. \(dp[n][x]\)를 문제와 같은 상황에서의 답이라고 하자. 우선 \(n>x\)면 모든 영웅이 한 번에 죽으므로 dp값은 \(x^n\)이다. 그렇지 않을 경우, \(y\)명이 생존했다고 가정하자. 그러면 \(dp[n][x]\)에 \(dp[n-y][x-y+1] \times (n-1)^k \times {n \choose y}\) 만큼을 더해줄 수 있다. 이를 모든 \(y\)에 대해 반복해주면 된다.

 

버츄얼이던 본 대회던 *2400 난이도 정도의 문제를 푸는 빈도가 늘어난 것 같아서 좋다. 지난 Div.1 B도 2500이 찍혔는데, 열심히 풀어냈음에도 불구하고 네 글자를 지우지 않았고 랜덤을 몰랐다는 이유로 레드 가는 라운드에서 1솔한 라운드가 되어버렸다. 레이팅에 너무 연연하는 것은 당연히 좋지 않지만, Div.1은 대회가 워낙 자주 없어서 이렇게 기회를 놓치면 슬픈 건 어쩔 수 없는 것 같다.