SCPC 2023 2차 예선 후기

풀이는 다른 고수분들이 잘 써줄 예정이니 짧게 후기만 적어보겠다.

 

딱 봐도 본선은 절대 못 갈 거 같다.

 

8시 반 쯤 일어나서 문제 1을 봤는데 너무 어려워서 침대에서 뒹굴거리면서 풀다가 잠에 들었다.

 

한 11시 쯤 다시 일어나서 생각해 보니까, 귀찮지만 그래프 만들어 놓고, 구현하면 될 거 같았다. 

 

구현해서 내니까 21점만 긁혀서 다시 생각해봤더니, 사이클 처리를 하면 될 거 같았다. 많이 더럽게 구현을 끝내고 한 1시쯤 100점 받았던 거 같다.

 

문제 2는 1시간 정도 보니까 풀이는 나왔다. 내 풀이는 누적합 + 세그 써서 모든 경우를 하나씩 찾는 풀이였다. 근데 자꾸 1.5초 + a의 시간이 나오는 거임..

그래서 상수 커팅 계속 하고, 세그로 비재귀로 바꾸고 별 거 다했는데도 1.5초의 벽을 뚫지 못하고 10번의 코인을 다 써버렸다.

 

 

근데 생각해보니까, 이거 N제한 200인 부분 점수도 안 긁힌 거 보면, N제한 200인 테케에서도 시간 초과 나는 거 아닌가?

내 풀이는 NlogN*a(a는 잘 모르겠어요) 정도라고 생각했는데, 내 생각보다 a가 많이 컸나 보다. 문제 2 푼 사람들은 어떻게 풀었는지 너무 궁금하다..

 

문제 2에서 알고보니 희망은 없었지만 희망 고문을 받고, 나머지 문제들을 풀러 갔다.

근데 진짜 두 번째거 못 풀었으니까 본선은 못 갈 거 같아서 의욕이 확 떨어졌다.. 그래서 컴퓨터 앞에서 좀 졸다가 다시 풀었다.

 

문제 3은 완전탐색으로 긁고,

 

문제 4는 2차원 DP로 긁고,

 

문제 5은 완전탐색으로 긁었다.

 

솔직히 문제 2 풀 사람들은 문제 3, 4, 5 다 저 정도는 긁었을 거 같다. 

애초에 문제 2 못 풀어도 문제 3, 4, 5 긁기가 너무 쉬워서.. 아무래도 본선은 내년을 기약해야겠다.

 

본선은 못가겠지만, 이런 대회라는 감을 잡았으니, 내년까지 계속하면 내년엔 갈 수 있을지도 모르겠다.

화이팅.