CodeTON Round 2 (Div. 1 + Div. 2)

티스토리에는 글을 처음 써본다.

여기에는 무슨 글들을 올리게 될지 아직은 잘 모르겠는데, 당분간 코드포스 버츄얼 기록들을 Informal하게 적어보려고 한다. 문제나 코드에 대한 설명은 따로 하지않고, 사고 과정을 돌아보고 피드백하는 과정을 주로 쓰게 될 듯 하다.

---

https://codeforces.com/contest/1704 이 셋을 돌았다. 2시간 30분짜리 셋이라 후반부쯤엔 조금 집중력이 떨어지는 것이 느껴졌다.

---

A. Two 0-1 Sequences [00:08:28]

일반적으로 Div. 2 AB나 Div. 1  + Div. 2 AB는 백도어를 찾는다는 마음으로 먼저 접근하는 편인데, 이 문제는 특별히 그런게 보이지 않아서 푸는데 조금 시간이 걸렸다. (문자열 B 길이) - 1 길이의 Suffix를 고정하고, 앞의 한 문자를 따로 매칭시킬 수 있는지를 판별해주면 된다. 구현도 조금 귀찮게 한 것 같다.

https://codeforces.com/contest/1704/submission/174936561

---

B. Luke is a Foodie [00:12:28]

어떤 선분이 통과하는 점들을 찾는 것 보다, 점들이 통과하는 선분을 찾는 것이 훨씬 편하다. V에 달린 X를 A_i로 옮기고 시작한다.

점을 구간으로 펼친 뒤에는, 구간의 교집합이 공집합이 될 때마다 V를 바꿔주는 그리디 전략을 택할 수 있다. 사실 왜 성립하는지 깊게 생각해보지는 않았다.

https://codeforces.com/contest/1704/submission/174936931

---

C. Virus [00:24:53]

N이 커서 수학적으로 접근해야 할 것 같은 느낌이 든다. 파라메트릭 서치를 잠시 생각해봤지만 별로 좋은 접근은 아닌 것 같아 관뒀다.

초기에 감염된 집들을 기준으로 감염되지 않은 집들의 영역이 M개 존재한다는 것을 이용한다. 그리고 모든 영역의 크기는 시간이 1만큼 지날 때마다 2씩 감소한다. 감소하는 속도가 모든 영역에서 동일하므로, 가장 넓은 영역부터 먼저 살리는 것이 이득임을 쉽게 보일 수 있다. 감염된 집들의 번호가 오름차순으로 안 주어진다는 사실을 조금 늦게 깨달아서 헤맸다.

https://codeforces.com/contest/1704/submission/174938015

---

D. Magical Array [00:54:05]

이 문제는 아이디어성 문제라 조금 더 빨리 풀었어야 했다.

배열의 수가 0 이하가 되지 않는다는 조건을 통해, 누적합으로 뭔가를 해보는 문제라고 생각할 수 있다. 

핵심은 op2를 적용했을 때 누적합의 합이 1 감소한다는 점이고, 이걸 얼마나 빨리 관찰하느냐에 문제의 모든 난이도가 달려 있다. 직접 연산을 시뮬레이션 하는 풀이도 있을 것 같긴 한데 잘 모르겠다.

https://codeforces.com/contest/1704/submission/174940642

---

E. Count Seconds [02:25:45]

간단하면서도 중요한 성질을 하나 짚고 가야 한다. a에서 b로 이동 가능하면 항상 a의 값들이 없어지는 시간은 b의 값들이 없어지는 시간보다 같거나 빠르다. 그렇지만 초기 상태에서는 중간중간 A_i의 초기값이 0인 지점들이 있기 때문에 위의 관찰이 잘 들어맞지 않는다. 게다가 A_i의 초기값이 모듈러 값과 정확히 같은 경우도 있어서 조금 조심해야되는 부분들이 있다. 한 1시간 정도 다양한 dp 풀이들을 생각해봤는데, 계산하기 너무 어려워 보여서 사실상 별로 진전은 없었다. 행렬제곱도 잠시 떠올리긴 했는데 이건 O(N^3)이 걸리기 때문에 포기했다.

위의 가정을 만족시키기 위해, N과 M 제한이 작다는 점을 이용한다. 초기 t < N 정도만 직접 시뮬레이션을 돌려주면 항상 위 가정을 만족하도록 A_i를 재구성할 수 있다. 이 과정에서 A_i가 모듈러를 취하는 과정에서 사라져버릴 수 있기 때문에 조심해야 한다. 나는 이 부분에서는 모듈러를 하지 않고 구현했다. 어차피 시뮬레이션 한 번에 A_i가 증가하는 값이 M을 넘지 않으므로 오버플로우 걱정은 안해도 된다.

어떤 정점으로 들어오는 간선이 a개가 있다면, t가 1이 증가할때마다 그 정점의 값은 (a-1) * t 만큼 증가한다. 이제 indegree가 0인 정점들을 차례로 제거해나가며 A_i 값들을 다시 재구성해나간다. 모듈러한 값이 작은 정점부터 제거하는 것이 옳은데, 왜 그런지는 조금 생각이 필요하다.

https://codeforces.com/contest/1704/submission/174951365

---

업솔빙은 어디까지 하게 될지 잘 모르겠다. 나중에 에디토리얼 읽고 구현해 보는대로 내용이 추가될 예정이다.