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

지난 대회에서 파이썬당한 이후 이번에는 C++로 C와 D를 풀려고 했으나 파이썬의 유혹을 이기지 못하고 이번에도 전부 다 파이썬으로 해결하였다. 하지만 오히려 파이썬을 씀으로써 D에서의 오버플로우 문제를 피해갈 수 있었다.

---

A: ConneR and the A.R.C. Markland-N

$0$으로 채워진 배열이 있고 배열에서의 현재 위치가 정해져 있다. 이 배열의 특정 위치들을 $1$로 바꿔놓았을 때, 현재 위치로부터 $0$이 있는 위치까지의 최단거리를 구해야 한다(사실 주어진 문제의 형식은 이와 좀 다르지만 앞의 설명과 본질적으로 같은 내용이다). 단순히 현재 위치로부터 양 옆으로 linear 하게 탐색하였다.

4분에 AC

---

B: JOE is on TV!

$n$명의 사람들을 대회에서 탈락시켜야 한다. 사람들은 여러 라운드에 걸쳐서 탈락하는데, 남은 사람 $s$명 중 $k$명이 탈락할 때마다 $\frac {k}{n}$씩의 상금이 더해진다. In the best case scenario, what is the maximum 상금?

 

$\sum_{k=1}^{n} \frac {1}{k}$이 정답이 됨을 예제를 보고 감으로 알았다. 각 라운드마다 가능한 선택지를 두고 부등호를 비교하면 수학적으로도 보일 수 있는 것 같다.

9분에 AC

---

C: NEKO's Maze Game

여러 문제에 단골 등장하는 $2 \times n$ 배열. 가로로 길게 펼쳐놓았을 때, 출발점인 왼쪽 아래로부터 도착점인 오른쪽 위까지 adjacent 칸을 통해 이동하고자 한다. 하지만 여러번의 query에 걸쳐 매번 특정 좌표가 [통행 가능] / [통행 불가]의 두 상태 사이를 toggle한다. Query가 들어올 때마다 그 resulting 배열의 상태에서 출발점에서 도착점까지 이동하는 것이 가능한지 판별해야 한다.

처음에는 $x$좌표의 각 경계마다 통행이 가능한지를 각각 기록해 두어야 한다고 생각했다. 빠른 시간 내에 모든 경계가 open되어 있는지 확인할 수 없을까? 하는 고민을 하다가 '어떤' 경계가 open혹은 closed되어있는지는 중요치 않다는 점을 깨달았다. Balanced parenthesis를 확인할 때와 같이, stack은 필요 없고 unclosed brackets의 count만 필요한 것이었다. 즉, 막힌 지점의 수를 계속 카운팅하며 매 query마다 그 수를 적절히 update해주면 된다.

 

풀이까지의 시간과 구현 시간 모두 빠르지는 않았다.

1 RTE 후 31분에 AC

(RTE는 trivial한 문제였다.)

---

D: Aroma's Search

숫자들 $x_0$, $y_0$, $a_x$, $a_y$, $b_x$, $b_y$ ($1 \leq x_0, y_0 \leq 10^{16}$, $2 \leq a_x, a_y \leq 100$, $0 \leq b_x, b_y \leq 10^{16}$)이 주어졌을 때, 모든 자연수 $k$에 대해 $$x_k=a_x \cdot x_{k-1} + b_x$$ $$y_k=a_y \cdot y_{k-1} + b_y$$이다.

좌표평면에서 $(x_k, y_k)$를 node라고 부른다($k$는 음이 아닌 정수, 고로 node는 무한히 많다). 주인공 Aroma의 출발점과 제한시간이 주어질 때, 1초마다 상하좌우 한칸씩 움직여 최대 몇개의 node를 방문할 수 있는지 출력해야 한다.

 

생각 전 예비단계: 시간 내에 도달 가능한 node들의 최대 개수는 worst case에 대략 50개이겠군. 한 node에서 다른 node로 이동할 때에는 시간 손실 없이 그 사이의 모든 node들을 다 방문할 수 있겠군.

 

첫 생각: 원점 부근에서 출발한다면 node들을 멀어지는 순서대로(즉, node들이 재귀적으로 정의되는 순서대로) 최대한 방문하면 되겠네.

 

다음 생각: node들이 나열되어 있는 공간 사이 어딘가에서 출발한다면 아래로(원점 방향으로) 혹은 위로(원점에서 멀어지는 방향으로) 가면 되겠네. 왔다 갔다 할 일은 없겠지?

 

다음 생각: 가장 가까운 node로 가서 무조건 아래로만, 혹은 위로만 가는 것은 solution이 아니네.

 

Solution: 근데 node의 개수는 50개잖아. 무조건 최단 거리로만 이동할테니 방문하는 첫 node와 마지막 node만 정하면 빠르게 총 소요시간을 구할 수 있겠어. 모든 조합을 확인해보면 되겠네!

53분에 AC

---

총평

감에 좀 많이 의존하긴 했지만 무난 무난하게 네 문제를 풀어냈다. E는 푸는 사람의 수가 한자리수로 유지되는 것을 보고 별 기대 없이 description만 읽었다. 네 문제를 해결하고 예상되는 레이팅 상승을 확인해보니 120정도로, 역대 최고의 상승폭이었다. 매우 만족스럽지만 한편으로는 퍼플을 아쉽게 못가는 상황이라 앞의 1 RTE가 안타까웠었다...

 

이런 대회가 끝나면 항상 하는 말이 있다: 다 해킹돼라!!

 

그런데 실제로 D의 구현에서 64비트 integer를 사용한 수많은 사람들(정말 많은 사람들이었다. 푼 사람의 절반 정도?)이 오버플로우 문제로 해킹되어버렸고, 내 등수는 91등에서 52등으로 급등했다.

 

이런 날은 또 갓파이썬이다. (파이썬: 오버플로우가 뭔데?) (지난 후기의 파이썬 혐오를 취소한다.)

 

레이팅 변화 1774 + 146 = 1920

My Performance: ★★★★☆

 

아직 안정적으로 유지하기는 힘들겠지만, 일단 퍼플이다!

방학 목표 달성은 덤.