Codeforces Round #722 (Div. 2)

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

 

 

코포 금단증이 점점 심해지던 차에 내가 선호하는 Div1+Div2 라운드가 나와서 기분 좋게 신청했다. 대회 당시 코 앞에 닥친 수행이 한두 개가 아니었는데, 이번 라운드는 절대 놓치고 싶지 않다는 생각이 들어 수행은 머릿속에서 지워버렸다. 그 여파로 대회가 끝나고 며칠 뒤인 지금 후기를 쓴다. 물론 지금도 밀린 수행이 쌓여있지만 난 모르겠다. 어떻게든 되겠지. 

 

 

Prob. A

최솟값이 몇 개인지 구하는 문제. 오랜만에 하는 대회이다 보니 문제가 잘 안 읽혀서 당황했다.

 

Prob. B

수학 느낌 나는 문제. 정확하지 않은 풀이 몇 개가 생각났는데 솔브 수가 빠르게 늘어나길래 그냥 제출해봤더니 맞았다. 정렬한 다음 앞에서부터 가능할 때까지 수열을 늘리면 그것이 최대 길이가 된다.

 

Prob. C

트리에서 뭘 구하는 문제인데, 이런 문제 특성상 양 끝의 값 중 하나를 택하는 것이 최적이다. 그리고 나서 루트의 값부터 정해주는 그리디 풀이를 작성하고 2틀을 박았다. 그리디가 정당한지도 잘 모르겠는데 트리 dp는 많이 짜 보지 않아서 시간만 엄청 쓰고 넘어갔다. D를 힘겹게 해결하고 다시 보니 그리디는 반례가 있을 것 같아서 트리 dp를 짜 보기로 했다. 시간이 많지 않아 대회 중에 제출하는 것을 목표로 정신없이 짰는데, 끝나기 2분 전에 완성한 코드가 한 번에 AC를 받아왔다!

 

Prob. D

대놓고 dp 문제. n=5 일 때의 케이스를 잘 나누었는데 덧셈을 잘못해서 틀린 점화식을 세우느라 시간을 엄청 썼다. n=100일 때의 값이 왜 나오지 않는지 고민하다가 점화식의 오류를 찾았다. 정확한 점화식은 dp의 누적합에 n의 약수의 개수를 구해야 했는데, 약수의 개수를 빠르게 구하는 것이 핵심인 것 같았다. 그리고 나는 약수의 개수를 n^(1/4)에 빠르게 구해주는 코드가 있었기에 자신 있게 제출했지만 6번째 데이터에서 TLE. 조금 당황했지만, 에라토스테네스의 체를 이용하면 약수의 개수도 빠르게 구할 수 있지 않을까 싶어서 검색해봤더니 바로 나왔다. 리브로님의 글에서 코드를 가져오니 AC.