Educational Codeforces Round 122 (Rated for Div. 2)

오렌지를 처음 찍은 후부터 이 라운드 전까지 총 3개의 rated 라운드를 쳤다. 결과는 -81, -9, -115로 많이 좋지 않았다.

 

첫 라운드에서는 A에서 크게 말렸고, Div.2 C에 세그를 두개 박는 오버오버킬을 하고 나서야 해결할 수 있었지만 그 때는 이미 대회 시작 후 1시간이 지난 시간이었기 때문에 좋지 못한 결과로 대회를 마무리해야 했다.두번째 라운드는 비교적 평이하게 진행되었으나, C를 4번 틀리고도 해결하지 못한 점이 아쉬웠다. 화룡점정은 본 글에서 다루는 라운드 바로 하루 전에 진행된 컨테스트였다. Div.2 였음에도 불구하고 2솔로 대회를 마무리했다. 퍼포먼스는 무려 민트였으며, 그런 경험은 굉장히 오랜만일 뿐더러 C가 그렇게 어려운 문제도 아니었기 때문에 멘탈이 나간 주 원인이 되었다.

 

세 라운드를 겪은 후 레이팅 변화는 2109->1904로, 자칫하면 오렌지에서 블루까지 떨어질 뻔 한 상태였다. 이러한 이유 때문에, 본 라운드를 치기 전에는 자존감이 상당히 떨어진 상태였다.

 

그렇게 치게 된 라운드의 결과

결과에 대해서도 할 말이 많지만, 우선 문제별 요약을 진행하도록 하겠다.

 

A. Div. 7 (00:01, +)

\(7 < 10\) 이기 때문에, 비둘기집의 원리에 의해 1의 자리수만 바꾸면 모든 수를 7의 배수로 만들 수 있다. 이를 구현할 때 i <= 9라 써야할 것을 i < 9라고 쓴 채로 제출해 잠시 당황했는데, 별 상관 없다는 것을 깨닫고 다음 문제로 넘어갔다.

 

B. Minority (00:04, +)

만약 초기 문자열에서 1의 개수와 0의 개수가 다르다면 둘 중 작은 것이 답이 된다. 만약 같은 경우에는 첫 문자를 제거하면 둘의 개수가 달라지므로 개수-1 을 출력하면 된다. 이 때, 문자열의 길이가 2인 경우에는 예외 처리가 필요하니 이에 주의하면 쉽게 해결할 수 있을 것이다.

 

C. Kill the Monster (00:13, +1)

어떤 시점 \(n\)턴째에서 몬스터가 죽어야 한다는 것을 다른 변수들과 \(n\)에 대한 부등식으로 나타낼 수 있다. 업그레이드 비용은 모두 사용하는 것이 항상 최선이니, \(k\)가지 경우에 따라 이를 모두 시험해보면 문제를 해결할 수 있다.

 

D. Make Them Equal (00:24, +)

각 숫자를 만드는 데 필요한 비용을 전처리하고 들어가면, \(O(nk)\) 냅색 DP 솔루션을 쉽게 찾을 수 있다. 다만, 이는 프리텟을 통과하기는 하나 시스텟에서 걸릴 가능성이 높은 풀이이다. 비용의 최댓값이 크지 않다는 점을 이용하면 \(k\)의 최댓값을 낮출 수 있고, 그보다 작은 경우에서만 냅색을 사용하면 안전한 시간 내에 통과하는 풀이를 만들 수 있다.

 

E.  Spanning Tree Queries (01:23, +)

쿼리의 개수가 \(10^7\)개이니 웬만하면 각 쿼리를 빠른 시간에 처리해야겠다는 생각을 할 수 있다. 

필요한 관찰들은 다음과 같다: 만약 간선의 가중치 순 정렬이 일정하다면, 고르는 간선 조합은 항상 같다.

이 각 간선의 가중치 순 정렬에 대해서 그 때 사용한 \(x\), 그리고 각 경우에서의 정답과 "고른 간선들 중 실제 가중치가 \(x\) 이하인 것의 개수를 안다면, 같은 정렬 상태를 사용한다는 가정 하에 정답을 \(O(1)\)에 구할 수 있다.

그리고 이 정렬 상태의 개수는 총 \(O(M^2)\)\)개이다. 다른 분들은 가능한 \(x\)가 각 가중치들의 평균이라는 사실을 알고 해결하셨던데, 내가 이를 알게된 생각의 과정은 조금 다르다. 만약 \(x\)가 어느 두 가중치 사이라면, 전체 가중치 정렬은 간선들을 원래 가중치가 \(x\) 이하인 것과 초과인 것으로 나눈 두 배열의 정렬과 같은 형식으로 나타난다. 각 경우에 대해 가능한 상황이 최대 \(O(M)\)이므로 총 경우의 수는 \(O(M^2)\)\)개 정도가 된다.

각 쿼리에 대해 알맞은 x를 찾는 데에 \(O(logM\)의 시간이 걸리므로 전체 문제를 \(O(M^3logM+klogM)\) 에 해결할 수 있다. 기본 예제와 프리텟이 꽤 탄탄해 보였고, 다행히 1트만에 문제를 해결할 수 있었다.

 

F는 도저히 풀 수 있을 거란 상상이 되지 않았고, 패널티 관리가 꽤 잘 되어 있었기에 거의 E를 해결한 직후 그대로의 등수로 대회를 마무리 할 수 있었다. 다행히도 핵이 터지지 않았고, Official 참가자 기준으로 10등이라는 결과를 받게 되었다. (+수정 : 누군가(들)의 치팅이 걸렸는지, 등수가 8등으로 올랐다.) 이런 높은 등수는 처음이라 꽤 놀랐을뿐더러 이전 3개의 라운드에서 떨군 200이 넘는 레이팅을 한번에 복구할 수 있었다. 또한, 하룻밤 사이에 퍼포먼스 차이가 1300이라는 이상한 사람이 되었다.

 

최근의 경험으로 코드포스와 나의 코딩 스타일에 대해 몇 가지를 깨달을 수 있었다.

 

1. Div. 2 기준 A~B, 또는 그에 준하는 난이도의 문제에 대해서는 말릴 일이 거의 없다시피 하게 되었다. 또한, 이러한 문제에 대한 해결 속도는 Div. 1 기준으로 보아도 괜찮은 편에 속하는 것 같다. 하지만 이는 Div. 1에 참가하게 된다면 별로 얻는 점이 없는 장점이라고 생각한다. 이러한 속도를 낼 수 있는 난이도의 한계선을 높이는 것이 중요할 것 같다.

 

2. 나는 만약 한 문제에 대해 처음 생각한 관찰이 틀렸을 경우, 이를 트는 데 어려움을 겪는 것 같다. 같은 이유로, 한 문제를 잡는 시간이 길어지면 (30분 이상) 문제 해결 능력이 크게 떨어지게 된다. 이를 해결하기 위해서는 직관을 증명해보는 습관을 기르는 것이 좋을 것 같다. 

 

3. 코드포스에 관해서는, BIT 연산을 사용하거나 GCD가 나오는 문제에 약하다. 적어도 코드포스에서 저 둘은 안 볼래야 안 볼 수가 없는 주제들이므로 연습이 많이 필요해보인다. 

 

4. 별로 중요한 부분은 아니지만, Friends Standing을 보다 보면 우리나라 코더들이 가끔 단체로 망하거나 단체로 흥하는 라운드가 있는 것 같다. 이런 부분을 분석해보면 라운드를 망칠 가능성이 조금이나마 낮아지지 않을까 싶다.

 

어떻게 다시 오렌지를 찍긴 했지만, 굉장한 운으로 올라온 것 같아 마음이 편하지는 않다. 오렌지를 유지할 실력이 되도록 더 열심히 공부해야겠다