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

요즘 대회를 하도 많이해서 슬슬 후기 남기기가 귀찮아지고 있다.

그래도 기록은 소중하니 소홀히 하지 않겠다.

---

A: New Year Garland

한번 엄청 빨리 문제를 풀어보고 싶다는 욕심이 들어 테케 수 입력 등의 코드를 미리 작성해놓고 문제만 빠르게 읽었다. R, G, B의 개수가 정해졌을 때, 같은 알파벳이 연속으로 나오지 않도록 일렬로 배열하는 것이 가능한지 판별하면 된다. 가장 숫자가 많은 알파벳을 떨어뜨리기 위해 나머지 두 알파벳 개수의 합이 충분한지만 보면 된다(i.e. more or equal to one less than the most frequent).

2분에 AC

---

B: Verse For Santa

정해진 시간 내에 릴레이식으로 최대한 많은 숫자의 노래를 불러야 한다. 총 제한 시간과 각 노래마다 소요되는 시간은 입력으로 들어온다. 노래는 입력 순서대로 불러야 하는데, 정확히 하나의 곡을 건너뛸 수 있는 찬스가 있다. 이때 어떤 곡을 건너뛰어야 하는지 출력해야 한다.

일단 누적합 배열이 필요할 것 같아서 각 곡까지 부르는데 걸리는 시간의 총합을 배열에 저장하였다. 이제 건너뛸 곡을 정해야 한다는 생각에 건너뛸 곡을 고를때마다 \(\log n\) 시간에 몇개의 노래를 부를 수 있는지 판별하면 되겠다는 판단을 하였다. 당연히 누적합 배열의 이진탐색으로 구현하였다. 정말 정신없게 풀고 증명 비슷한 것도 해보지 않은 풀이라서 통과할 수 있을지 많이 걱정하며 제출하였다. 1번의 WA는 bisect_right 대신 bisect_left를 써서 발생하였다.

1 WA 후 18분에 AC

 

대회 종료 이후 다른 사람들의 풀이를 보니 \(O(n)\) 풀이가 정해인 듯 하다. 누적 최댓값 배열만 만들어준다면 linear 하게 진행하면서 누적 최댓값을 누적합에서 빼주면서 제한 시간 내에 들어오는지만 확인하면 되는것이었다. 이보다 이진탐색 풀이를 먼저 떠올린 이유는 건너뛸 곡을 heuristic으로 정하지 못할 것이라고 생각한 까닭이었다...

---

C: Stack of Presents

Stack of presents라길래 설마 그 스택인가 했는데 그 스택이 맞다. 중복되지 않는 선물의 스택이 있고, 발송해야 하는 선물의 목록이 있다. 목록의 선물을 순서대로 스택에서 꺼내야 하는데, 스택에서 선물 하나를 꺼낼 때마다 그 위에 쌓여있는 모든 다른 선물을 들춰내고, 목표의 선물을 빼낸 뒤, 들춰낸 선물들을 다시 올리는 수고를 반복해야 한다. 이때 다행히 추후에 꺼내게 될 선물들을 고려하여 조금의 optimization을 할 수 있으니(다행인건지는 모르겠다. 이 조건이 없으면 문제를 풀 일도 없겠지?), 선물들을 다시 쌓을 때에는 원하는 순서로 쌓을 수 있다.  최적의 optimization을 했을 때, 몇번의 loading and lifting을 해야 하는지를 구해야 하는 문제다.

 

뭔가 복잡할 것 같았으나 모든 문제를 푸는 필살 기법인 '종이에 직접 수행해보기'를 해보았더니 한번 마주친(i.e. 한번이라도 지나가면서 건드린) 선물들은 무조건 원하는 턴에 나타나도록 설계할 수 있는것이 보였다. 따라서 발송해야 하는 선물을 하나씩 살펴보며, 마주친 적이 없다면 그 위치를 linear search로 찾아주고, 마주친 적이 있다면 정답에 1을 increment 해주면 된다. \(O(n^2)\)의 복잡도를 피하기 위해서 linear search는 아직 탐색하지 않은 스택의 깊이(?)부터 아래 방향으로 시작하도록 하자(이것을 안해주어서 TLE를 받았었다).

1 MLE 1 TLE 후 36분에 AC

---

D: Santa's Bot

$n$명의 사람들 각각에 대한 wish list가 있다. 각 wish list에는 원하는 선물의 번호가 중복 없이 들어가 있다. 서로 다른 두 사람중에서는 같은 선물을 원하는 사람이 있을 수 있다. 근데 상태가 좀 이상한(?) Santa의 bot은 임의의 사람을 고른 후, 그 사람의 wish list에서 임의의 선물을 고른 후, 다시 임의의 사람을 골라 방금 고른 그 선물을 줘버린다. 이렇게 동작하는 Santa의 bot이 앞 문장에서 설명한 방식대로 선물 하나를 발송했을 때, 그 선물이 선물을 받은 사람이 원하던 선물일 확률을 구해야 한다. 확률이 $\frac x y$의 꼴로 표현된다면, $x \cdot y^{-1} \mod 998244353$을 출력해야 한다. 확률을 구하는 방법은 각 선물의 등장 빈도를 first pass에서 세주고, second pass에서 확률을 계산해 더해주는 two-pass method이다. $O(nk)$이라서 통과할 줄 알았으나 결론부터 말하면

5 TLE 4 WA

를 받고 대회 종료되었다. 파이썬이라서 당한 줄 알았지만, 사실 파이썬이라 당한 줄 알아서 당한 것이었다. 알고리즘 자체가 느려서 통과 못하는 것을 언어 때문이라고 생각해 똑같은 문제있는 알고리즘을 C++로 다시 구현하는 삽질을 반복하고, TLE와 WA를 골고루 받아냈다. 조금만 시간을 들여 생각했다면 두 가지를 알 수 있었을 것이다. 첫째, 이 문제는 분수 계산을 직접 하다보면 분모와 분자의 크기가 너무 커진다. 둘째, $x \cdot y^{-1}$의 값은 분수의 곱셈과 덧셈 전에 적용하여 곱하고 더해도 유지된다. 이런 사실들을 항상 대회 종료 직후에 보인다. 수정한 코드는 파이썬과 C++로 모두 통과시켰다. (내 알고리즘 실력보다는 파이썬을 믿자..)(방금 파이썬당하고 왔다)

---

총평

E와 F는 푼 사람이 거의 없었고, A, B, C는 무난하게 처리하여 D만 잘 풀면 되는 상황이었는데, 이런 상황일수록 잘 되는 경우가 없는 듯 하다.

빠르게 풀고 싶은 욕심에 머리보다 손이 먼저 나가 금방 해결할 D를 끝까지 풀지 못하게 되었다.

 

레이팅 변화 1756 - 23 = 1733

My Performance: ★★☆☆☆