SCPC 2017 본선 후기

2016년 이맘때쯤엔 코딩에 대한 흥미를 아예 잃어버렸던 터라 SCPC를 참가하지 않았는데 올해에는 참가했습니다. 프로그래밍은 2016년 겨울부터 다시 꾸준하게 했지만 1차 127점, 2차 29?점이라는 다소 저조한 성적으로 본선에 진출했기 때문에 높은 상은 전혀 기대하지 않고 19~38등에게 주는 5등상이라도 받기를 기대했습니다.

1시 반에 대회가 시작이었고 참가자들에게는 늦어도 1시까지 오라고 공지가 되어있었습니다. 요새 수면주기가 완전 망해버린 터라 10시 반쯤 일어났고 밍기적대며 아침을 먹고 대회장으로 이동했습니다. 대충 12시 50분쯤 도착해서 자리에 착석했습니다. 각자 자기의 자리에서 제한 없이 컴퓨터를 테스트해볼 수 있었는데, 문제는 인터넷이 열려있어서 마음만 먹으면 외부의 코드를 대회 시작전에  마음껏 다운받아놓을 수 있었습니다. 실제로 그렇게 한 사람은 없었겠지만 이 점은 다음 대회때 시정이 필요해보입니다.

대회가 시작된 이후 바로 1번 문제를 봤습니다. 문제들의 배점은 200 / 300 / 450 / 550이었고 2, 3, 4번 문제는 읽지도 않았습니다. 1번 문제는 꽤 간단한 sliding window 문제였고 거의 모든 참가자가 만점을 받았습니다.(아마 2명인가 3명빼고 모두 만점을 받았을 것입니다.) 예선을 보셨던 분은 알겠지만 각 문제의 정답자수가 실시간으로 공개되었고 저는 대략 70번째로 1번 문제를 풀었습니다. SCPC는 ACM ICPC와 다르게 동점자간의 순위 경쟁에서 문제를 풀어낸 시간은 그다지 중요하지 않기 때문에 70번째로 풀어낸 것에 대해 그다지 개의치 않았습니다.

2번 문제는 두 볼록다각형 A, B가 주어질 때 두 볼록다각형의 distance를 구하는 문제였고,(최대 200000각형)

• 두 볼록다각형을 잇는 가장 짧은 선은 반드시 어느 한 볼록다각형의 점을 지난다.
• A의 임의의 한 점 P에 대해 B의 변 중에서 이웃한 두 변과 P의 거리보다 자기 자신과 P의 거리가 더 짧거나 같은 변은 가장 짧은 distance를 가지는 변 밖에 없다.

이 두 성질을 이용해서 풀 수 있습니다. 자잘한 코딩 실수와 두 점 사이의 거리를 구할 때 int 범위를 벗어날 수도 있다는 것을 망각하고 짰다가 여러번 날려먹고 8번 만에 맞췄습니다. 말고도 A의 각 점에 대해 볼록다각형 B로 최단 거리에 가는 경로끼리는 서로 만나는 점이 없다는 성질을 이용해 convex hull로 풀이가 가능하다고 합니다.

3번 문제는 subtask 2번(N <= 1000? 2000? 가물가물..) 까지는 그냥 2중 for문으로 풀 수 있고 N <= 200000은 다이아몬드 영역에서 포함하는 점들의 갯수를 plane sweeping오로 알아내야 한다는데 전 못풀었네요.

4번 문제는 애초에 정답자가 2명인 문제였습니다. cycle이 없는 subtask만 맞춰서 37점을 받았습니다. 굉장히 복잡한 문제이고 직접 여러가지 경우에 대해 부딪혀보면서 Case by case에 대해 깨달음을 얻어나가야 합니다. 당연하게도 저는 못풀었습니다.

1번 정답자 125명, 2번 정답자 36명, 3번 정답자 39명, 4번 정답자 2명이고 저는 3, 4번을 부분점수만 조금 긁었기 때문에 수상은 힘들겠구나 싶었는데 정말 간당간당하게 끄트머리에 걸려서 5등상을 받았습니다. 1, 3번만 풀고 2, 4번에서 부분점수를 아예 못받은 사람이 여러 명 있었나봅니다.

사실 제 실력은 아직 좀 애매합니다. 적당한 난이도의 문제들은 잘 접근하지만 세그먼트 트리, Network Flow, 2-SAT, SCC와 같은 어려운 난이도의 자료구조/알고리즘의 경우에는 개념은 알고있지만 아무 것도 없는 상태로 구현을 하라고 하라고 한다면 그닥 자신은 없는 상태입니다. 즉 아직 공부가 부족합니다. 그럼에도 불구하고 끄트머리나마 5등상을 받을 수 있었고 실력에 비해 과분한 상을 받은 것에는 잘 안떠오르는 문제에 대해 빠르게 부분문제를 긁은 것이 유효한 것이 아닌가 하는 생각이 드네요.

대회뿐만 아니라 이런저런 행사들도 참가자의 입장에서 너무 형식적이거나 과하지 않고 딱 적절하게 잘 진행된 것 같습니다. 또한 앞으로 공부할 것이 정말 끝도 없겠다는 것도 느끼게 됐네요.