SCPC 2019 후기

아직 병특 3년+학교 2년이 남아 있어 SCPC에 올해 빼고도 5번은 더 참가할 수 있는데 수상기회는 2번밖에 없어 그냥 최대한 편하게 할려고 했다. 상 탈 수 있으면 좋은거고 못타면 내년에 더 잘할 때 더 좋은 상 타는거고.. 결과적으로는 616점으로 커트라인에 걸려서 바라는 대로 수상하지 못했다(?). 내년을 노린다..!

 

A - 예선 A번으로 나왔어도 적당한 난이도 같다. 딱히 할 말은 없다.

 

B - 좌표평면에 점들이 주어지고 그 점들을 잘 이어 단순다각형을 만드는데 그 단순다각형의 둘레를 최대한 크게 만드는 최적화 문제. 나는 컨벡스헐 만들때 쓰는 그 좌표정렬을 하고 순서대로 이어서 193점을 받았다.

 

공식 풀이가 꽤 재미있었는데, lower convex hull을 하나 만들고 남은 점들을 x좌표가 증가하는 순으로 잇는 것이다. 생각해보면 문제에서 점들이 랜덤으로 배치함이 주어지기 때문에, x좌표가 증가하는 순으로 이을 때 y좌표는 랜덤하게 진동(?)할 것임으로 둘레가 점 하나 이을때마다 꽤 많이 늘어날 거 같다. 문제 조건을 똑똑하게 써먹는 것의 예시?

 

C - 왼쪽/오른쪽 자식 구분이 없는 BST가 하나 주어지고, 두 노드의 비교 결과가 하나씩 늘어날 때마다 가능한 BST의 개수를 그때그때 계산하는 문제이다.

 

풀이 자체는 꽤나 만들어내기 쉽다. 처음에는 2^(internal node개수)만큼의 경우의 수가 있고, 제한이 하나 증가할 때 마다 제한이 "a가 b의 왼쪽에 있다" 라고 하면 (문제의 말은 좀 달랐지만 같은 말이다) a와 b의 lca로 가서 자식의 방향을 잘 지정해주며 경우의 수에 나누기 2 또는 "이제 불가능함" 판단을 적절히 해 주면 된다. 처음에는 subtree dp쪽으로 뻘짓을 좀 했는데 경우의 수가 어떤 상황에서 얼마나 증가하는지 조금만 생각해보면 그렇게 복잡할 문제가 전혀 아님을 알 수 있다.

 

진짜 문제는 내가 입력을 다 읽지 않고 다음 테케로 넘어갔고+LCA구현 실수(LCA(a, b)를 구하면서 a, b가 각각 LCA(a, b)의 어느 쪽 자식인지 구해야 하는데, 중간에 swap(a, b)를 하고 어느 쪽 자식인지 리턴하는 부분은 swap을 도로 안해줬다)로 인해 맞왜틀을 마음속으로 외치며 제출 20번+3시간을 날려먹었다.

 

D - 왼쪽, 오른쪽으로 각각 r길이를 커버할 수 있는 기지국들이 L길이의 선 위에 주어지고, 목표는 기지국에 선 전체를 커버하는 건데, 그러기 위해서 기지국이 움직여야 하는 거리의 합의 최소값을 구하는 문제.

 

그리디하게 빈틈을 채우는 게 정해였다고 하는데, 듣고 보니 꽤나 간단했는데 정작 대회중에는 그런 방향으로는 아예 생각이 나지 않았다. 대회중에는 "최종적으로 겹치는 구간의 길이가 정해져 있으니까 겹치는 구간의 길이를 거기에 맞춰보자" 쪽으로 좀 생각을 해봤는데, 별 진전이 없어서 C번을 디버깅하러 돌아갔다. (..) 아무래도 이건 문제를 너무 복잡하게 rephrase한 느낌이다. 결국 문제의 목적은 모든 구간에 기지국이 있는거고 - 그럴려면 빈틈이 없어야하고 - 그럼 빈틈을 최대한 메워보자! 이런 식으로 돌아돌아 가지 말고 생각했으면 생각났을려나?

 

E - 뭔가 3차원 좌표평면에서 PPAP를 추면 2차원으로 줄여지고 거기서 "피와 땀과 눈물"을 통해 풀 수 있는 문제라고 한다. 난 이해할려고 하지 않았다. :fearful:

 

끝! 작년보단 잘 했으니 내년엔 더 잘 해야지..!