Codeforces Round #694 (Div. 1) 후기

Codeforces Round #694 (Div. 1)

---

A. Strange Birthday Party

처음엔 감도 안 잡혀서 포기할까 생각하다가 조금 더 고민해보니 \(c\)를 기준으로 이분탐색할 수 있다고 생각했는데
그렇게 거의 다 짜고난 뒤에 안 된다는걸 깨달았다.

그래서 더 고민해보니 \(k\)를 기준으로 정렬한 뒤 앞에서부터 몇번째까지는 현금으로 주고 나머지에게 선물을 주는 식으로 계산을 할 수 있었다.
그리고 그 방식이 가능한 시점은 이분탐색으로 찾을 수 있다.
이렇게 구현했는데, 구현도 매끄럽게 안 되고 심지어 냈는데 한 번 틀리기까지 해서 이미 멘탈이 나갔다.

 

B. Strange Definition

보자마자 소인수분해하고 각 소인수의 개수의 홀짝이 모두 같은 쌍이 인접한 거라는건 알았는데 일단 소인수분해 자체가 내 방법으로는 아무리 봐줘도 \(300,\!000,\!000\)번은 연산이 필요해서 소인수분해는 아니다로 시작해서 고민을 해봤다.
근데 아무리 고민해봐도 소인수분해가 필요한 문제여서 하기로 결정하고, \(w=0\)인 경우 외에는 모두 쿼리의 답이 같다는건 금방 찾아서 그렇게 구현했다.
그런데 구현도 계속 틀리고 찾는 것도 오래걸리고 쩔쩔매다가 다 고쳤는데 시간초과가 떴다.
그래서 소인수분해를 조금 최적화해서도 내보고 추하게 폴라드-로를 오늘 처음 찾아보고 내봤는데도 시간초과가 떴다...

그렇게 못 풀고 대회도 끝났고, 그러고나서 좀 고민해보니 미리 소수를 찾아놓은 뒤에 소인수분해를 하면 시간이 꽤 빨라진다는 것을 놓쳤었다. 자주 썼던 방법인데 전혀 생각을 못했다...

+ 각 수의 최소 소인수를 저장해두면서 체를 쓰는 방법도 있다. 곱셈적 함수를 계산할 때 쓰이는 방법이기도 하다.

---

 

어차피 마스터 유지할 생각도 없었고 떨어진대로 올려야겠다 생각은 했지만 예상보다 훨씬 더 망해서 슬펐다. 이번이 말린거였으면 좋겠다.