Codeforces Round #701 (Div. 2)

Dashboard - Codeforces Round #701 (Div. 2) - Codeforces

 

 

꽤 만족스러운 라운드였다. 느린 3솔을 했는데, 문제가 어려웠는지 높은 퍼포먼스를 받았다. 이로써 블루 복귀를 1트 만에 성공했다. 오늘은 발 뻗고 잘 수 있을 것 같다.

 

Prob. A

보자마자 간단한 수학 or 애드혹 문제인 줄 알았다. 그래서 생각나는 풀이를 몇 개 적어봤는데 전부 예제가 안 나왔고, 예제로 디버깅하기에는 예제가 더러워서 그냥 다음 문제로 넘어갔다. B 풀고, C 풀고, D 고민하다가 넘어와서 다시 보니 대충 작은 b들에 대해서 다 해보면 되겠다는 생각이 들었다. 최적해가 아닌 경우가 있을까봐 걱정했지만, 시간이 없어서 그냥 제출했더니 맞았다. 다른 사람들 풀이가 궁금해서 바로 락 걸고 읽었는데 다 이렇게 풀었더라. 허허..

 

Prob. B

O(nk) 풀이는 자명하지만 안될게 뻔하고, sqrt나 log는 안 붙을 것 같아서 O(n) 풀이를 찾으려고 했다. O(nk) 풀이를 식으로 나타내고 열심히 식 정리를 하면 각 쿼리를 O(1)에 처리할 수 있다.

 

Prob. C

처음에 문제를 (a/b) mod b == a mod b로 읽어서 엄청 헤맸다. 식 정리하니까 뭔가 규칙이 나와서 문제를 잘못 읽었다는 생각은 죽어도 못했고, 일반항을 찾으려고 애쓰다가 포기하고 문제를 다시 읽었다. 보니까 내가 생각한 방식대로 하면 예제도 안 나와서 뭔가 잘못되었다는 걸 깨달았다. 제대로 해석한 문제는 간단했고, 마찬가지로 쉽게 규칙을 찾을 수 있었다. 일부 구간에 대해서는 O(1)로 구할 수 있고, 나머지 구간은 (x/(k+2))+(x/(k+3))+...+(x/(y+1)) 과 같은 짓을 해서 구해야 했는데, naive 하게 구하면 TLE 날 것 같아서 같은 몫을 가지는 부분을 빠르게 더하는 트릭을 사용했다. 사실 얼마 전에 사용해본 스킬이라 빠르게 떠올릴 수 있었다.

 

 

내가 그토록 원하던 완벽한 수학 셋이 등장했지만, 기대만큼 성적이 잘 나오지는 않았다. A에서의 뇌절과 C에서 해석 실수만 없었다면 D까지 풀 수 있었을 것 같아 아쉽다. D 같은 아이디어성 문제를 놓치는 것을 보면 내 창의력이 점점 떨어지고 있는 것 같아 슬프다.