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

피곤한 날은 퍼포먼스가 확실히 떨어지는 듯 하다.

---

A: Sum of Odd Integers

2분에 AC

---

B: Princesses and Princes

구현 문제.

빠르게 구현하여 11분에 제출하였으나, 배열 초기화 작업이 $O(n)$인 것을 간과하여 $O(n^2)$ 코드를 제출하였다.

C++로 바꿔서 구현하면서 시간만 더 뺐기고, C++ 솔루션이 TLE를 받고 나서야 문제점을 발견하였다.

이 문제만 아니었어도 레이팅이 올랐을 듯 하다.

3 TLE 이후 37분에 AC

9분 걸릴 문제를 35분 걸려서 푸는 마술

---

C: Game with Chips

얘도 별거 없다. 왼쪽 아래로 모든 칩을 몰아준 후 모든 칸을 방문하면 된다.

$mn + n + m - 3 \leq 2nm$이 모든 자연수 $n$, $m$에 대해 성립하므로(증명은 사실 안해봤다 ㅎ) 이러한 풀이가 가능하다.

1 WA 후 52분에 AC

무려 $m$과 $n$을 헷갈려서 틀렸던 것이다...

---

D: Infinite Path

푼 사람이 적으므로 스킵!

했다가 다시 돌아왔는데 못풀었다.

---

E: Count The Blocks

$n$이 주어지면, 0부터 $10^n - 1$까지의 숫자를 적는다. 이때 모든 숫자는 길이가 $n$이 되도록 0로 적절히 padding한다.

각 숫자에서, 동일한 digit이 연속해서 반복되는 것을 하나의 block으로 지칭한다.

Task는, 모든 숫자에서 block의 개수의 총합을 길이별로 세는 것이다.

 

우선 떠오른 생각은 $n$번째 솔루션이 $n - 1$번째 솔루션과 연관성이 있을 것 같다는 것이었다. 예시 입력을 보니, $n=1$일 때의 결과값 $10$이 $n=2$일 때에도 반복되고 있었다. 이에 나는 증명 과정을 건너뛰고, $n - 1$번째 솔루션이 $n$번째 솔루션의 뒷부분이 된다고 가정했다. 그렇다면 $n$번째 솔루션의 첫 항만 계산하면 되는데, 이는 모든 block 길이의 총합이 $n \cdot 10^n$인 것을 이용해 누적합을 적절히 기록하면 된다.

Proof by AC.

1시간 16분에 AC

---

총평

졸리면 코포 하지 말고 잠이나 자자.

 

레이팅 변화 1973 - 17 = 1956

My Performance: ★★☆☆☆

---

연습지