2020 SNUPC 후기/풀이

SNUPC 2020 Division 2에 참가해서 3등상 (7등) 을 했다. 작년과 성적에는 큰 차이는 없지만 작년보다 Div2 참가자들의 인적인 풀이 더 상승한 것 같으므로 (= 대회가 더 추해진 것 같으므로) 그럭저럭 괜찮았다고 생각한다. 3시간 동안 아무것도 못한건 매우 아쉽지만 풀이를 듣고 보니 그럴만했었다고 생각한다.

---

대회가 로딩 되자 마자 문제 탭을 쭉 켰는데, A는 Tab이 crash해버려서 B를 먼저 읽었다. B는 구현 문제인데, 일단 대차게 한번 틀리고 시작했다. Frustration은 오늘도 계속된다... 그래도 초반 문제들의 난이도가 어렵지 않으므로 빠르게 제정신을 되찾..는거까진 아니고 그러려고 노력할 수는 있었다. 빠르게 A를 다시 켜서 A를 먼저 풀었다.

---

A. 수면 패턴

AC : 13 min

월/화/수/목/금을 0/1/2/3/4로 생각하면, '월요일 0시부터 흐른 시간' 으로 날짜/시간을 바꾸어 생각할 수 있다. 그렇게 하면 모든 interval의 길이 합을 쉽게 구할 수 있고, 약간의 예외처리만 해주면 쉽다.

---

이 사이에 B를 한번 더 틀리고 몹시 화가 난 채로 C번을 읽으러 갔다.

 

C. 넴모넴모 2020 

AC : 21 min (First Solve)

가로 방향과 세로 방향으로 지워지는 넴모의 개수를 따로따로 세자. 가로 방향은 $a_{y_i} - x_i$ 로 쉽게 셀 수 있다.

세로 방향의 경우, $a_y$ 들을 보면서 어디부터 내가 보는 열 $x_i$에 넴모가 없는지를 파악할 수 있다. $y_i$ 들이 단조감소함이 주어져 있으므로 Binary search를 사용하면 $O(q \log n)$ 에 해결할 수 있다.

---

D를 읽었으나 잘 모르겠다는 생각이 들어서 E를 읽었다. 쉬워 보여서 바로 풀었는데 약간의 실수를 했다.

 

E. 여우 신탁

AC : 41 min (First Solve)

첫 여우에게는 $[0, x_1)$ 범위의 정수가 랜덤하게 하나 주어진다. $n$ 라운드에 걸쳐, $x_i$가 주어지면, $i$번째 여우에게는 전 여우에게 내려준 수를 modulo $x_i$ 한 값을 내려주게 된다. 마지막 여우에게 내려줄 숫자의 기댓값 구하기.

Naive하게 생각해 보자. $[0, x_1)$ 범위의 정수를 처음에 하나만 고르고 나면 그 다음의 모든 과정은 사실 이미 정해져 있다. $O(nX)$ 시간에 모든 가능한 값들을 트래킹하면 되는데, 구체적으로는 $[0, x_1)$ 범위의 모든 인덱스에 +1을 해놓고 이것을 확률값의 가중치로 보기로 하자. 예를 들어 주어진 숫자가 5, 3 순서라면, [1 1 1 1 1]로 생각해 놓고, 그다음 과정을 수행하면 [1 2 2] 가 될 것이다.

$O(nX)$ 는 당연히 시간 초과를 받게 된다. 위 상황을 조금더 관찰해 보면, $x_i$가 한번 들어오면 모든 가능한 숫자들이 그보다 작아지게 된다. 그리고, 그 이후에 더 큰 숫자가 들어오더라도, $x_i < x_j$ 라면 $x_i$ 부터 $x_j$ 까지의 숫자는 어차피 나올 수 없으므로 무시해도 된다.

즉, 각 숫자가 나올 확률 가중치 값을 들고 유지하는 과정에서, '가능한 최댓값' 에 대한 정보를 관리한다면, 오른쪽에서부터 이 '가능한 최댓값' 정보를 밀면서 나아갈 수 있다. 나아가는 방향이 단조적이므로 $O(n + X)$ 시간에 모든 확률 가중치를 계산할 수 있다.

 

'가능한 최댓값' 을 $[0, x)$ 로 관리할지 $[0, x-1]$ 로 관리할지에 대해 생각하다가 실수로 한번 틀렸다. 그외엔 별로 어려움은 없었던 듯

---

아직도 B를 맞지 못한 채로 D를 풀러 갔다. 분명 기억에는 D를 30분 정도 풀었고, B를 그 사이에 슬쩍 내서 맞았다고 기억하고 있었는데 스코어보드를 보니 D를 먼저 맞았었네.. 남은 180분 간 고통받아서 기억이 꼬인듯 하다

 

D. 신기한 연산

AC : 64 min

어떤 길이 $M$의, $N$종류 알파벳으로 구성된 문자열을 만들어서, $2N-1$ 홀수 길이의 부분 문자열을 아무렇게나 하나 골랐을 때, $N$종류의 알파벳이 모두 나와야 하며, 그중 홀수번 나오는 것이 유일해야 한다. (원래는 구간들이 주어져서 그 구간에만 만족하면 되는데, 그런 지나치게 어려운 construction은 답이 없다. 가끔 나오는 유형으로, 어떤 집합 A의 원소를 하나 찾아야 하는 문제에서, 집합을 A의 부분집합인 B로 줄이고 B의 원소를 하나 찾음으로 대신할 수 있다)

이런 construction은 생각이 나면 재밌지만 20분동안 나름 hard thinking해서 얻었는데 무슨 생각을 했었는지 과정이 별로 없다. Construction을 잘하기 위해서는 생각을 정리하고 논리적으로 나아가는게 중요한데 그게 부족해서...

aabbccddeeffaabbccddeeff...하면 된다. ($N = 6$일 때 예시)

---

마지막으로 B를 맞았다. 왜 이렇게 구현력이 갈수록 떡락하는가? Python으로 짰는데도...

 

B. 단어 개수 세기

AC : 68 min

시키는대로 잘 자르면 된다. 나는 ==을 써야 하는 일에 startwith를 써서 한 번, h가 모음으로 처리해야 한다는 것을 제대로 안 읽어서 한 번, qu'[문자열]'[문자열]'[문자열] 같은 이상한 케이스를 처리하지 않아서 한 번 틀렸다.

구현할때는 침착하게, 작은 단위로 머릿속으로나 또는 Explicit하게 체크하면서 나아가자.

---

남은 180분의 시간 동안 F, G, I 등을 고민해봤는데 코딩까지 나아가지 못했다.

F의 경우, set을 가지고 미친듯이 PPAP추는 이상한 알고리즘을 생각햇으나 구현하지 못할 것이라는 확신이 들었고, 실제로 구현한다고 쳐도 그다음은 백트래킹을 어떻게 할지 모르겠길래 접었다.

G는 11차원의 위압감 때문도 있지만, 2차원이었어도 잘 모르겠기 때문에... 

I번은 Segment Tree with Lazy propagation을 써서 푸는 문제라고 생각했으나 F에서 시간을 소모하느라 구체화하지 못했다. 사실 결과론적인 이야기지만 이거에 전력투구했으면 풀 수 있었을 것 같다.

 

내년엔 Division 1 나가야지..!!