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

잠시 과제와 시험이 없는 틈을 노려 무려 두달 반만에 코드포스 대회를 접수했다.

---

A: Reorder

문제를 해석하는 순간 사실상 끝난다. Reordering은 낚시.

2분에 AC

---

B: Prime Square

여러 가지 풀이가 있는 듯 하다. 나같은 경우, $1$을 $n - 1$개 배열한 후, 더해서 소수가 되는 숫자 하나를 더 추가해 하나의 행을 만들었다. 이 행을 한칸씩 밀어 배치해주면 square가 완성된다.

13분에 AC

---

C: Binary Search

풀고 나서 보면 꽤 쉬운 문제인데, 이런 생각을 해본 적이 없어서 뇌정지가 잠깐 왔었다.

 

직접 이진탐색을 해보며, 찾고자 하는 값보다 왼쪽과 오른쪽에서 확인하게 되는 원소의 수를 기록하면 된다.

왼쪽과 오른쪽에서 확인하는 원소의 수가 정해지면, 경우의 수를 계산하는 것은 쉬운 문제가 된다.

39분에 AC

---

D: Bandit in a City

시키는대로 구현하여 알 수 없는 복잡도의 풀이를 만들었다.

TLE를 연거푸 받아 계속 최적화를 시도하였으나, 더 빠른 $O(n)$ 풀이가 있었다.

 

트리의 모든 노드에 대해서 $\lceil \frac {S}{L} \rceil$를 계산해, 최댓값을 취하면 된다. 이때 $S$는 그 노드를 루트로 하는 subtree에 있는 사람 수의 총합이고, $L$은 같은 subtree에서 leaf의 개수이다. $\lceil \frac {S}{L} \rceil$는 그 subtree안에서 최대한 균등한 분배가 이루어졌을 때의 결과값인데, 만약 이러한 균등한 분배가 일어날 수 없는 상황이라면 현재 살펴보고 있는 노드의 child 중 사람들이 더 '몰리는' 노드 $M$이 존재한다. 현재 살펴보고 있는 노드에서 $M$쪽으로 사람을 더 보내지 않을 것이기 때문에, 노드 $M$에서 다시 $\lceil \frac {S}{L} \rceil$값을 계산해주면 된다.이런 방식으로 재귀하는 것을 생각하면, $\lceil \frac {S}{L} \rceil$값의 최댓값이 정답이 되는 이유를 알 수 있다.

 

결국 못풀고 끝났다.

---

총평

D번을 풀지 못해 레이팅이 하락하였다.

하지만 나 혼자 못푼것은 아니라서, 딱히 평상시보다 못한 것 같지는 않다.

 

다시 블루 구경할 뻔했다.

 

레이팅 변화 1935 - 18 = 1917

My Performance: ★★★☆☆

---

연습지