Codeforces Round 942 (Div. 1)

Dashboard - Codeforces Round 942 (Div. 1) - Codeforces

 

사실 전 글은 쓸 생각이 없었는데, 이번 대회를 치고 이 글을 쓰기 위해 전 것도 작성했다. 하아

 

Prob. A

원소의 최소 개수를 최대화해야 함은 직관적으로 알 수 있다. 그리고 예제를 통해 그 원소의 개수의 역순으로 배열하는 것이 최적임도 알 수 있다. 그래서 이를 이분탐색 등을 이용하여 잘 구현해주면 되는데, 자꾸 틀린다. 도저히 틀린 부분이 안 보여서 B를 다 풀고 왔더니 이분탐색 시작할 때 천장 값을 너무 크게 잡은 게 오버플로우를 유발하는 것 같았고, 실제로 그 부분만 고치니 맞았다. 이런 실수 되게 오랜만에 하는 것 같다.

 

Prob. B1

식을 정리해보면 나이브가 루트 시간에 돈다.

 

Prob. B2

식을 정리해보면 나이브가 대충 루트 시간에 돈다.

 

Prob. C

$f$의 역함수를 구하고 빠르게 거듭제곱하면 될 것 같이 생겼다. 일단 역함수 또는 역행렬은 어렵지 않게 유도할 수 있다. 이제 행렬을 제곱시켜야 하는데, 직접 거듭제곱을 해보니 규칙이 보일 듯 말듯 보이지 않는다. 예전 같았으면 어떻게든 찾아냈을 텐데 왜 그랬을까... 규칙을 찾는 데에 실패했으니 거듭제곱을 빠르게 할 다른 방법을 찾아야 한다. 요즘 학교 선대 강의에서 마침 대각화를 배우고 있어서 대각화를 쓰면 행렬의 거듭제곱을 쉽게 할 수 있다는 것이 생각났다. 그래서 $8 \times 8$ 행렬의 대각화를 시도했는데 왜인지 대각화가 되지 않는다. 현실을 부정하고 대각화를 계속 시도하다가 겨우 정신을 차렸다. 그러나 구글링을 더 하다가 이런 글을 발견했고, 뭔가 그럴 듯 해서 꼼꼼히 보다가 마지막에 가서야 전혀 도움이 안 된다는 것을 깨달았다. 결국 다시 규칙 찾기로 돌아와서 보니 인덱스 차의 비트 수에 따라 기여도가 조합으로 결정된다는 것을 발견했다. 대회 종료 12분 전이었지만, 규칙이 간단해서 충분히 맞을 수 있다고 생각했다. 열심히 코딩한 결과 2분 전에 코딩을 마칠 수 있었는데, 왜인지 예제가 나오지 않는다. 그래서 급한 마음에 무지성으로 이것저것 고치다가 결국 실패했다. 끝나고 차분한 마음으로 다시 보니 너무 당연한 부분을 놓치고 있었고, 이를 확인해 주는 한 줄만 추가하니 맞았다.

 

이번 라운드를 치면서 실력이 많이 떨어졌음을 느꼈다. 문제 푸는 감이 죽은 건 아닌데, 디테일이 부족하다고 해야 하나... 이런 꿀 수학 라운드에서조차 레이팅이 떨어지면 정말 가망 없는데.. 너무 아쉽다