SCPC 2023 본선 후기

 

본선 4등상 수상하였습니다!

 

 

 

1번 문제를 보았습니다.

 

처음에는 살짝 어려울줄 알고 쫄았는데 홀짝성만 봐도 끝나는 문제였습니다. 바로 짜서 맞췄습니다.

 

(0:10) 1번 +100점

 

 

 

 

 

2번 문제를 보았습니다.

 

열심히 생각을 정리하니 로봇은 항상 가장 근거리에서 만나야지만 최선임을 이용해서 DP식이 세워지고, 이 직선의 형태가 CHT로 변형될 수 있다는것이 어렵지 않게 떠올랐습니다. 개인적인 감상으로는 문제 발상 자체는 난이도가 낮았어서 많이들 생각했지 않았을까 싶습니다.

 

 

그걸 바탕으로 우선 O(N^2)인데 CHT로 바로 변형 가능하도록 코드를 짜는데.. 어라 생각보다 쉽지 않습니다. 구현이 너무 빡셈을 느끼고 겨우겨우 짰지만 오답이 나왔습니다.

 

(1:20) 2번 WA

 

 

이때 살짝 멘붕이 왔습니다. 왜냐하면 코드를 개떡같이 짜놔서 디버깅 해야 할 것이 산더미인데, 제가 사전점검도 안해와서 디버깅조차 제대로 할 수 있는 상황이 아니였기 때문입니다. 그래도 제 구현능력을 어느정도 믿어보고 이것저것 훑어봤지만, 아무리 봐도 틀린게 없었습니다.

 

 

멘탈이 펑 터진채로 아니 나만 못푸는건가? 싶어서 돌아왔더니 2번 정답자수는 0명이였고 왠 4번이 많이 풀려있었습니다.

 

 

휴~ 그럼 그렇지 ㅎ 하고 4번으로 갔습니다.

 

 

그런데 4번은 더더욱 멘탈이 터졌습니다. 뭘 해야 할지 머리가 띵 해졌습니다.

 

 

가장 큰 숫자를 a라고 할 때 양쪽으로 나뉘는 특징과, 가장 작은 숫자를 a라고 할때 양쪽의 특징을 살펴보며 접근했는데, 제 문제풀이 경험으로는 이럴 때 큰 숫자를 기준으로 하는 경우를 많이 봤어서 큰 숫자일때 특징을 위주로 살펴봤습니다. 열심히 식을 정리했더니 O(N^4)짜리 DP식이 나왔습니다. 오... 심지어 공간복잡도도 O(N^4)이라 그냥 답이 없었습니다.

 

 

이게 아닌거 같은데 싶으면서도 제 문제풀이 경험으로는 이 풀이밖에 없다는걸 본능적으로 알고있었어서 더 나아가지도 못하고 빼지도 못하는 상황에서 1시간이 더 흘러갔습니다.

 

 

아 제대로 말렸구나 싶어서 조금 있다가 다시 보는편이 좋을 것 같아 다시 2-2로 넘어왔습니다.

 

 

다행히도 2-2의 오류가 여러개 보이기 시작했습니다. 제가 바보같은 전처리를 몇개 해놓은 바람에 반례 데이터를 찾을 수 있었습니다.

 

겨우 2:40쯔음에 눈에 보이는 오류들을 고치고 다시 제출했습니다. 하지만 오답이 나왔습니다.

 

(2:40) 2번 WA

 

 

 

이젠 진짜 멘붕이 왔습니다. 3시간째가 됐는데 제 점수는 100점이고 그냥 아무생각도 나지 않았습니다..

 

정말 이대로는 망한다 하면서 2-2의 반례데이터를 무지성으로 만들어봤습니다. 그러다가 운좋게 하나가 얻어 걸렸습니다. 잠깐 고민해 보니, 로봇을 정지해 두고 나중에 바꿔치기 하는것이 이득인 경우가 추가로 있었습니다. 이에 대한 처리를 해 주었고, 이번에는 141점이 나왔습니다.

 

(3:00) 2번 +141점

 

 

 

그래도 141점을 맞으니 희망이 보였습니다. 이 상태에서 4번만 맞아도 5등상은 받겠다는 생각이 들었습니다. 그래서 4번 문제를 아얘 처음부터 차분히 접근을 했습니다.

 

 

그런데 왠걸, 처음에 생각했던 큰수 작은수 중에서 작은수를 기준으로 점화식을 고민해보니 엄청 쉽게 식이 나왔습니다. 울부짖으며 코드를 작성했고 바로 만점이 나왔습니다.

 

 

(3:20) 4번 +200점

 

 

이 문제는 후에도 복기를 정말 많이 했습니다. 제가 왜 말렸는지도 좀 고민을 해 보았고.. 다시는 말리지 않도록 점검을 많이 했습니다.

 

 

아무튼 시간이 30분이나 주어졌습니다. 저는 이제 두 가지 선택지가 있었습니다.

 

 

이미 풀이를 아는 2-3을 긁기 vs 3번을 파기

 

 

둘다 유효한 선택지였다고 판단했습니다. 왜냐하면 저는 2-3에도 자신이 있었고 3번은 트리문제인데 저는 트리문제에 한해 슈퍼 무적이기 때문에 30분따리여도 다 긁어버릴 수 있을거라는 자신이 있었습니다.

 

 

먼저 2-3을 해보자는 결론을 내렸고, 잠깐 고민해보니 생각보다 만만치 않음을 느꼈습니다. 왜냐하면 로봇이 멈추는 쿼리가 추가되면서 컨벡스헐이 기울기가 감소하는 방향으로만 주어지지 않았기 때문입니다. 잠깐 이것저것 끄적여 봤는데 유의미한 결과를 얻지 못했고 아쉽게도 15분정도를 버리게 되었습니다.

 

 

나중에 돌이켜 보면 그냥 두개의 컨벡스헐을 만드는게 유효한 전략이였고, 정말 최근 코드포스에서도 한참 심화된 버전이 나온적이 있었는데 (https://codeforces.com/contest/1866/problem/K) 시간에 쫓겨 빠르게 포기한게 살짝 후회됐습니다.

 

 

3번으로 걱정없이 가게 된 것은, 제가 트리에 무한한 자신감이 있던 것도 한몫했어서.. 뭐 다시 돌이켜도 같은 선택을 하고 있었을것 같기는 합니다.

 

 

3번을 읽어봤습니다. 그런데 생각보다 심상치 않았습니다. 각 서브트리에서의 최선의 전략을 찾아내야 할것 같았는데 잘 정리되지 않았습니다. 10분정도 더 고민해봤는데 안떠올라서, 너무 아쉽지만 3-1이라도 긁어보겠다고 열심히 코드를 짰습니다. 그런데 틀렸습니다.

 

후에 보니 급히 짜다가 테케가 여러개인 것을 고려하지 않고 입력을 받는 바람에 메모리 초과가 났던 것으로 정리됐습니다.

 

 

 

 

총점 441점을 받았고, 복기를 해보면서 너무 초기접근을 이상하게 했거나, 시간에 쫓겨 허투른 판단을 했던 것들이 많이 보여 아쉬움이 많이 남았습니다.

 

 

 

무엇보다 총점이 너무 애매했어서 (4등상 - 5등상 사이 어딘가) 5등상을 받으면 슬플 것 같았습니다.

 

 

하지만 대회 끝, 수상식! 다행히도 4등상 턱걸이를 했네요... 정말 다행입니다. 좀 말렸으면 어때요 4등상 받았으면 그만이야~! 이제 저는 다시 행복해졌습니다.