2024 정보올림피아드 고등부 2차

수능 공부 끝에 다시 돌아왔습니다. 이번 5월에 1차에서 동상을 받아서 본선에 진출하게 되었습니다. 정시 때문에 딱히 준비를 하진 않았고 대회 1~2주 전 즈음에 재활을 조금 했습니다.

 

생각보다 좋은 결과를 받았습니다. 아직 가채점 결과가 나오진 않았지만 운이 좋으면 은상을 노려볼 수 있지 않을까요?

 

14:21:16 가로등(1번) 100점

대회는 13:30분에 시작했습니다.

시작하고 1번 문제를 읽었습니다. 일단 구간을 적당히 $2N$개로 쪼개서 최솟값을 관리해줄 수 있는 자료구조에 넣고 $K$번 뽑아주면 될 것 같았습니다. 구현을 딱히 생각 없이 하다 조금 틀리고 1시간 정도 지나서 100점을 받았습니다. 쉬운 문제였는데 구현도 말리고 오래 걸려서 이때까진 대회가 망한 줄 알았습니다.

 

16:27:34 xor 최대(2번) 100점

2번을 읽었습니다. 문자열 문제길래 진짜 대회가 망한 줄 알았습니다. 어제 지인이 문자열 연습 하자고 셋을 파주었는데 귀찮아서 던졌던 기억이 나며 후회스러웠습니다. 일단 문제를 읽어보니 뭔가 쉽진 않아보였습니다. $N = 10^7$이길래 일단 십덕문자열비비기 는 아닌 것 같았습니다. 1시간 정도 넘어서 $O(N^2)$정도 되는 풀이를 짜고 디버깅을 했지만 계속 0점이 나와서 멘탈이 나갔습니다. 손이 벌벌 떨리고 아무것도 못하겠는... 그러다 뭔가 보이기 시작했습니다. 그리디하게 생각하면 케웍을 2가지 정도만 하면 답이 나왔습니다. 그러나 평소 케웍만 보면 던지고 그리디면 또 던지던 제가 이걸 맞을 자신은 없었습니다... 일단 반쯤 속는 셈 생각해보면 케웍을 다 하고 제출했습니다. 0점이 떴고 저는 좌절했습니다. 조금 진정하고 디버깅을 하려 보니 구간을 구하는 코드에서 오타가 있었습니다. 그것만 고치니 바로 100점이 떠서 이때부터 슬슬 잘풀리는 것 같은 기분이 들었습니다.

 

16:41:08 트리 뽑아내기(3번) 100점

3번을 처음 읽었을땐 아무것도 모르겠어서 2번으로 다시 돌아갔었습니다. 이제 2번을 풀었으니 3번을 조금 더 열심히 읽기 시작했습니다. 예제를 손으로 시뮬레이션 하다 보니 루트에서 우선순위큐를 들고 대충 하면 답이 나오는 것 같았습니다. 가정이 맞았는지 확인하기 위해 제출했는데 100점이 나와 당황스러웠습니다. 3번을 15분컷 정도 한 것 같습니다.

 

16:50:44 점수 경주 2점(4번) (섭태 1)

일단 문제를 읽었습니다. $N = 300000$, tl 6.5초, 모든 경로를 고려해야하는 트리문제? 이건 무조건 센트로이드 분할이다 == 내가 절대 풀태를 못푼다 라는 가정하에 섭태를 열심히 긁기 시작했습니다. 우선 자명한 $O(N^2)$ 섭태를 짰습니다.
17:21:24 점수 경주 4점(4번) (섭태 4)

누적합 + 이분탐색으로 4번 섭태를 긁을 수 있을 것 같아 짰습니다. std::lower_bound 쓰는 법을 까먹어서 그냥 이분탐색을 짰습니다.
17:30:43 점수 경주 6점(4번) (섭태 2)

리루팅dp로 2번 섭태를 긁을 수 있을 것 같아 짰습니다.

 

그 후 3번 섭태의 풀이를 조금 고민해봤지만 가중치가 뭔가 이상해서 잘 모르겠었습니다. 나중에 들어보니 오타였다고 하네요... 조금 아쉽습니다. 

적당히 할게 없고 퇴실도 못해서 뻘짓을 좀 하다 대회가 끝났습니다.

 

312점... 은상 가능할까요? 가채점이 화요일에 나온다는데 그때까진 떨려서 잠을 못 잘 것 같습니다. 학교 플젝도 해야하는데 고민이네요...

 

후기

제 2번째 정올이자 마지막 정올입니다. ps를 조금 늦게 시작해서 아쉽긴 하네요. 준비도 별로 못하고 요즘 자존감도 낮아서 아무 생각이 없었는데 생각보다 잘본 것 같아 기분이 좋습니다. 뽀록도 실력인걸까요? 

 

ps가 저에게 주는 의미는 꽤 컸습니다. 수능 준비를 시작하고 ps를 접은 후에는 조금 줄어들긴 했지만... 제가 자발적으로 무언가를 한 경험이 그렇게 많지는 않았거든요. 노력을 한 성과가 그래도 보인 것 같아 기분이 좋습니다.

 

은상을 받게 된다면 특기자로 ist계열을 써볼 생각입니다. 카이스트... 는 솔직히 안될 것 같고 unist gist dgist 중 하나는 붙지 않을까 하고 기도를 해봐야겠네요.

 

수능 또한 버릴 수 없어 보입니다. 특기자는 아무래도 도박성이 너무 심해서... 여름방학때 열심히 해야겠죠? 정시 성적이 너무 안나와서... 고민이 많긴 한데 자신감을 얻었습니다. 수능 끝나고 다시 오겠습니다.

 

추가)

굳