Codeforces Round #775 (Div. 1, based on Moscow Open Olympiad in Informatics)

"그 리저널"

전날 있던 Div. 2에서 2095->1943이라는 기염을 (또) 토한 터라 멘탈이 좋지는 않았다. Div. 1에서 오른 적이 거의 없던 터라 좀 무섭기도 했고.. 그래도 레이팅이 엄청 낮아져 있었기 때문인지 어떻게 오르긴 한 것 같다.

 

A. Weird Sum (00:38, +)

Div. 1에서의 흥망을 가르는 요인은 A라고 생각한다. 그리고 나는 대부분의 Div. 1에서 A만 보면 뇌가 굳는다. 이번 역시 그랬다. 스코어보드는 10분만에 초록색이 쫘르륵 깔리는데 나는 감이 하나도 안 왔다. 30분을 넘게 생각한 후에야 정해도 아닌 \(O(NsqrtN)\) 시간복잡도의 풀이를 찾아서 해결할 수 있었다. 이때만 해도 엄청 망할줄 알았다.

 

B. Integral Array (01:01, +1)

문제를 처음 봤을때 숫자의 최댓값에 대한 제한이 걸려있는걸 보고 크게 어려운 문제는 아닐거라 생각했다. 분모를 \(x\)로 고정하면 \(C/x\)개의 몫 후보가 나오게 되고, Harmonic Lemma 때문에 모든 \(Ai\)에 대해 이 과정을 진행해주어도 시간 안에 문제를 해결할 수 있다. 나는 분자 확인을 누적합이 아니라 이분탐색으로 해서 로그가 하나 더 붙었는데, 시간제한이 2초라 다행히 통과되었던 것 같다.

 

C. Tyler and Strings (01:28, +1)

전날 앳코더에서 비슷한 문제를 봐서 접근은 어렵지 않게 할 수 있었는데, 식 정리(정확히는 그에 따른 전처리)를 하는게 조금 귀찮았다. 누적합과 팩토리얼의 누적합에 대한 펜윅 트리를 만들면 어렵지 않게 문제를 해결할 수 있다.

 

A, B, C중 A를 푸는데 가장 많은 시간이 걸렸다. A를 늦게 푼거 말고는 크게 퍼포먼스에 하자가 없다고 생각했는데, 시스텟에서 많은 사람들이 내려갔음에도 오렌지 퍼포가 안나오는걸 보면 Div. 1이 대단하거나 지역의 한계이거나.. 둘 중 하나인 것 같다.