2019 SCPC 본선 후기

7월 30일에 열린 2019 SCPC 본선

작년에도 SCPC 본선을 참가했지만 수상은 못 했었다. 이제 대학원을 입학해야 하는데 대학원이 얼마나 바쁠지, PS 공부를 계속 해나갈 수 있을지 확신이 없기 때문에 사실상 마지막 대회라는 생각으로 임했다.

사진을 거의 못찍어서 인증샷은 유튜브 동영상 캡쳐로 대체한다. (제일 왼쪽이 나)

https://youtu.be/NG8CbnECy5w

SCPC는 기념품이 아주 많고 좋은데, 저기에 있는 노트북만 빼고 다 가져가면 된다. 키보드, 마우스, 장패드, 가방, 노트, 펜을 준다.

11시부터 1시까지는 사전 등록 시간이었다. 나는 늦잠을 잔 탓에 12시 정도에 도착했다.

작년과 마찬가지로 아는 사람이 없어서 멀뚱멀뚱 있었다. 극한의 아싸체험.. ^^

그나마 작년 SCPC에서 친해져서 팀연습도 같이 하고있는 재찬이가 있어서 묵언수행은 안할 수 있었다.

사전 등록 시간에는 아주 자유분방한 분위기인데, 먼저 과자/과일/음료가 아주 많아서 먹으면서 수다를 떨어도 되고, 컴퓨터를 미리 세팅하기도 한다.

한쪽에서는 삼성 채용 상담과, 삼성 소프트웨어 멤버십 상담을 진행하고 있었다. 대학원에 진학하는지라 채용 상담은 일단 건너뛰었고, 삼성 소프트웨어 멤버십은 관심을 가지고 있던 터라 재찬이랑 같이 가서 간단히 상담을 받아봤다. SCPC 수상자는 코딩 전형이 면제된다고 이번에 꼭 상을 받으라고 말해주셨다.

먹을 것을 조금 먹고 컴퓨터 세팅을 먼저 했는데, 세팅 난이도가 참 어렵다(...)

올해도 작년과 마찬가지로 visual studio와 codeblocks가 깔려 있었는데

평소 visual studio를 쓴다면 크게 상관은 없겠지만 평소 GCC를 사용한다면 #include <bits/stdc++.h>를 사용하지 못하는 것부터 __builitin_, __gcd 등을 사용하지 못하는 소소한 문제가 생긴다.

codeblocks를 사용한다면 GCC를 사용할 수 있는데, 디버깅할 때 stl 내부가 안보이는 치명적인 문제점이 있었다. 여러 방면으로 해결하려 시도를 해봤는데, 결국 실패했다. cmd를 켜고 gdb를 하면 잘 보이는데 codeblocks에서는 왜인지 안보인다.

혹시라도 환경에 조금 민감한 사람이라면 일찍 도착해서 자신에게 최선의 환경이 되도록 미리 세팅할 것을 권장한다. 세팅에 실패한 나는 결국 codeblocks와 visual studio를 둘 다 켜놓고 코딩은 codeblocks로, 디버깅은 visual studio를 사용했다.

1시 반에 대회를 시작했다. 총 4시간짜리 대회였다.

A번

먼저 A번을 켰는데, 작년 주사위 문제 정도를 생각하고 있었는데 이 무슨 말도 안되는 꿀문제가 하나 있었다.

사실 내가 문제 이해를 잘못한 거고 사실 최대 이분 매칭 문제가 아닐까도 생각을 했는데, 그러기에는 n이 너무나도 컸다.

재빨리 코드를 작성하면서 보니 만점자 수가 빠르게 늘고 있었다. 이를 보고 그냥 꿀문제인 게 맞다는 것을 확신하였다. 이후 제출하고 7분 정도에 AC.

C번

이후 B번을 열었는데 휴리스틱 문제인 것 같아서 C번을 먼저 보았다.

이진 트리에서 누가 누구의 자식인지 정보가 주어지는데, 이 때 가능한 이진 트리의 수를 구하는 문제이다.

이후 m개의 쿼리가 들어오는데, a번 노드가 b번 노드보다 값이 크다는 정보를 담고 있다. 이 정보를 누적하여 만족하는 이진트리의 갯수를 차례대로 구해야 한다.

모든 가능한 경우의 수를 합하고 1e9+7로 나눈 것이 답이다.

조그마한 관찰을 하면 알게 되지만, 리프 노드가 아닌 노드가 하나 있을 때마다 경우의 수가 2배씩 늘어난다.

조건이 주어질 때마다 a번 노드와 b번 노드의 LCA에 해당하는 노드의 자식의 방향이 고정된다.

새롭게 고정되면 경우의 수를 2로 나누고, 모순이 생기면 0으로 만들면 된다.

LCA와 그 바로 아래 child의 정보를 빠르게 알아내야 했지만 다행히 이진 트리라서 코딩이 그리 어렵지는 않았다.

대략 50분 쯤에 문제를 다 풀어냈다. 예감이 좋은데(?) 하며 제출했는데, WA.

이때부터 약 1시간 30분 동안 지옥의 디버깅이 시작됐다.

정말 할 수 있는 디버깅은 모두 다 해봤다. 트리의 모든 pair별로 LCA를 모두 출력해보고, 요상한 모양의 트리를 만들어서 넣어보고 했는데도 다 잘 돌아갔다.

혹시 이상한 예외(가령 a == b인 노드가 들어온다거나)가 있나 해서 생각할 수 있는 모든 예외를 모두 생각했음에도 코드는 돌아가지 않았다.

망했음을 예감하고(ㅠㅠ) 낙담하고 있는데 불현듯 머릿속을 스치며 왜 틀렸는지 이유를 알아냈다.

SCPC는 한 번에 테케가 여러 개 주어지는데, 예외 처리를 할 때 테케에 해당하는 입력을 다 받지 않고 바로 동작을 그만두도록 코딩을 했던 것이다. 이런 초보적인 실수는 원래 잘 안하는데, 백준이랑 코포 스타일에 익숙해져 있었는지 초보적인 실수를 하고야 말았다. 그렇게 내 1시간 넘는 시간은 사라졌다. 바로 수정해서 제출하니 AC.

B번

어차피 페널티도 망한 것 같은데 그냥 포기할까 생각했다.

앞에서는 ainta 님이 2시간만에 올솔을 한 스코어보드가 떠다니고 있었고, 스코어보드 끝자락(15등 정도) 사람들은 1, 2, 3번을 다 풀어내고 4, 5번 small 테케를 다 긁은 상태였다. 문제를 푸는 도중에는 올솔을 한 koosaga 님이 위풍당당하게 시험장을 나가는 모습이 보이는 등 정신적인 압박이 상당했다.

B번은 랜덤한 50~100개의 점이 주어지는데, 점을 적당히 잘 이어서(다 쓸 필요는 없다) 단순다각형을 만드는데 변의 길이의 합을 최대로 만들어야 한다. 최댓값을 만드는 것은 다항 시간 내에 해법이 알려져 있지 않다고 하고, 적당히 큰 값을 찾아내야 하는 휴리스틱 문제이다.

휴리스틱 문제에서 꽤 잘 작동하는 해결법은, 적당히 그리디한 솔루션을 하나 적용해보는 것이다. 혹시 초깃값에 따라 local maximum에 도달하고, global maximum에 도달하지 않을 가능성이 있으니 초기값을 선택하는 과정을 여러 번 반복하면 좋은 결과를 얻어낼 확률이 조금 더 높아진다.

나는 일단 삼각형에서부터 시작하여, 다음 그림과 같이 특정 변을 점 하나를 더 추가하여 길이를 늘릴 수 있는 모든 경우를 찾고, 그 중 길이가 가장 많이 늘어나는 경우를 적용하였다. 이를 모든 점이 다각형에 포함될 때까지 반복해주었다. (다각형이 있고 어딘가에 점이 있을 때, 어떠한 점은 적어도 한 변에 대해 저 방법을 적용하는 것이 가능하다)

150점 정도라도 나오면 다행이라고 생각하며 제출하였는데, 왜인지 200점이 떠버렸다. 어라? 갑자기 수상의 가능성이 보였다.

참고로 끝나고 알려준 B번의 풀이는, lower convex hull을 찾은 뒤 convex hull에 포함되지 않은 점들은 지그재그로 이어주는 것이었다. 상당히 깔끔하다.

대충 점을 찍어서 내 방법이랑 저 방법이랑 어떤 게 더 결과가 좋은 지 비교해봤는데, 내 방법도 그리 완전히 나쁘지는 않은 것 같았다. 역시 승리의 막코딩~ 애초에 휴리스틱 문제가 조금 운빨이 강하다.

이제 40분 정도가 남았고, 어쩌면 수상을 할 수 있을지도 모른다는 생각이 들었다.

패널티가 작지 않으니 최소 D번, E번의 소문제 하나씩은 풀어야 B번에서 195~199점 정도를 맞은 사람들을 제칠 수 있을 거라는 생각이 들어서 남은 시간 안에 D, E번의 소문제를 꼭 풀어내야하는 상황이었다. 심적으로 압박감이 매우 심했다.

D번 (Group 1)

주변 r 반경 내의 영역을 커버할 수 있는 포인트 n개가 주어질 때, 0~L의 영역 전체를 커버하도록 포인트를 적당히 옮겨야 하는데 이동거리의 합이 최소가 되어야 한다. 이 때 이동거리를 출력하는 문제이다.

풀이는 정확히는 이해가 안갔고, 대략 그리디하게 접근하면 되는 것 같다.

다행히 Group 1의 문제들은 n * 2 * r = L을 만족한다. 즉, 모든 point가 있어야 하는 위치가 딱 정해져있다.

따라서 point들을 그냥 sorting하고 이동거리의 합을 구하면 된다.

E번 (Group 1)

3차원 공간 속에 점이 적당히 흩어져있다. 다음과 같은 조건을 만족하는 정육면체 두 개가 존재한다.

i) 정육면체의 중심이 같다.

ii) 모든 점은 작은 정육면체 바깥에 존재 (경계도 가능)

iii) 모든 점은 큰 정육면체의 안에 존재 (경계도 가능) 

이 중 두 정육면체의 변의 길이의 차이의 최솟값을 구하는 문제이다.

역시 갓문제라서 풀이는 이해가 정확히는 되지 않았다.

무언가 잘 하면 3차원 문제를 2차원으로 축소시킬 수 있고, 이후 피와 땀과 눈물을 통해 답을 구해낼 수 있다고 한다(실제로 한 말)

Group 1은 x, y, z의 좌표가 -10~10 사이에 있다는 행복한 조건이 붙어있었는데, 따라서 모든 점을 다 중심으로 고려해보면 답을 빠르게 찾아낼 수 있다. 정수점과 정수 + 1/2인 점 모두를 고려해야 하는데, 복잡도는 41^3 * n이므로 충분하다.

집중력을 유지하여 D, E번 Group 1 문제도 풀어냈다. 이 때 이제 수상에 대한 확신이 들었다.

결과적으로 653점으로 5등상을 수상하게 되었다.

5등상의 컷은 616점, 4등상의 컷은 653점이라고 한다. 나는 코딩이 꽤 빠른 편이기 때문에 만약 LCA에서 말리지 않았다면 충분히 4등상도 가능성이 있었다고 보지만, 내가 4등상을 받을 실력은 아닌 것 같으니 5등상을 수상한 것에 감사한다.

스코어보드에 그리 압박감을 가질 필요도 없는데, 2회 이상 상을 수상한 사람들은 1등이 아니라면 수상자에서 제외된다. 덕분에 조금 더 유리한 고지를 얻었던 것 같다.

SCPC를 포함한 다양한 코딩대회는 대략 1등상~3등상을 IOI 한국 대표, ACM-ICPC 한국 대표가 나누어 가져가는 대회 느낌인데, 수많은 굇수들 사이에서 수상을 했다는 것이 아주 만족스럽다. 명예의 전당에 내 이름과 DGIST의 이름을 남길 수 있다는 것도 좋다. 또한 소멤 가입이나 여러 채용 전형에서 우대사항이 있을 수도 있겠다. 그래도, 나 자신이 아직은 실력이 많이 부족하다고 느끼니 어디에서나 찾는 사람이 될 때까지 더 열심히 공부해야겠다.

190820 추가)

이번에는 다소 늦게 codeground 사이트가 업데이트 되었다

https://www.codeground.org/contest/contest

올해부터는 외국 대학교 학생들도 참가가 가능해진건지, 하버드 대학교와 미시간 대학교가 상당히 눈에 띈다.

저기 적힌 순서는 100% 확률로 등수 순서이다. 따라서 나는 23등이다. 물론 2회 수상자가 제외된 등수이므로 실제로는 30등을 넘어가지 않을까 생각한다.

수상자를 보고 있으면 많은 생각이 든다. 올해 1~9등까지는 베트남 한 분을 제외한다면 모두 다 서울대이다. 꼭 올해만 그런 것은 아니다.

현재까지 열린 5회의 대회 중 중복을 포함하여, 총 175개의 상 중 67개를 서울대학교에서 가져갔다. 3대장인 서울대, KAIST, 고려대에서 가져간 상의 비율은 무려 70%가 넘는다. 명문대가 단순히 이름만 있는 건 아니라는 것을 뼈저리게 느끼게 해주는 대목이다.

우리 학교 다음 수상자는 언제쯤 나오려나~