2019 ACM-ICPC Seoul Regional 참가 후기

대회 망한 4솔따리지만 꾸역꾸역 써봅니다...

 

서론)

작년에 대회를 같이 나갔던 팀원들은 다들 군대라든가, 타 대학원이라든가 멀리 떠나갔고, 새로운 팀원들 2명을 구해서 3달간 그래도 정기적으로 연습을 해보았다.

이번에는 i) 문제 푸는 것을 재미있어하고, ii) 열심히 할 사람들을 기준으로 팀원을 구했는데, 그리 좋은 기준이었는지에 대해서는 의문이 든다.

팀원들이 석달간의 연습을 통해 코포 블루 중위권(1700점 정도)까지는 올라와주는 것이 목표였지만, 실력이 생각보다 잘 늘지 않아 결국 1500점도 아닌 1200점 언저리에 위치한 팀원들을 보고 그닥 대회에 대한 의욕이 많이 생기지는 않았다...

여담으로 만약 한 번의 기회가 더 주어진다면 이번에는 수학을 잘 하는 사람들 위주로 팀원을 구해보지 않을까 생각된다.

 

나도 잘하는 건 아니지만 어차피 코포 1500점 넘는 사람 한 명 없는 학교에서 예선 통과는 확실해 보였고, 예선 6솔이 목표였지만 nlognlogT에서 로그를 하나 떼지 못해 5솔로 찝찝한 본선 진출을 확정지었다.

 

 

본선)

특별상이 초기 공지에는 2팀으로 나와있었는데, 4팀으로 늘어나있었다. 작년에 특별상 8팀 중 6등으로 특별상을 수상했었으니, 뭐.. 작년보다는 내 실력이 늘은 걸 감안하여 만약 다양한 학교가 장려상 안에 포함이 되고, 문제가 나랑 잘 맞고, 팀원들 포텐이 터진다면 아예 가능성이 없다고 생각하지는 않았다.

 

이번 티셔츠는 파란색이었는데, 작년의 주황색보다는 외견상으로 나아보이긴 했지만, DGIST 학생들이라면 조정부를 떠올릴 법한 색깔이었다.

 

올해는 작년 경험이 있기도 하고, 리눅스 환경에 익숙해져 세팅같은 데에서 헤매지는 않았다.

 

 

A. Fire on Field

꿀문제. 대회마다 꿀문제가 하나는 있기 마련이고, 빨리 찾는 것이 대회의 묘미 중 하나이다.

앞에 놓인 풍선을 보고 F번 I번이 꿀문제일 것이라 예상했는데 어림도 없었다.

A번은 팀원 중 한 명이 읽고 있었는데, 결국 스코어보드를 보고 꿀문제임을 알아냈다.

 

 

J. Triangulation

정다각형이 주어지는데, 이를 삼각형으로 분할시켰을 때, 삼각형 pair 사이의 거리 중 최댓값이 가장 작은 분할을 찾는 문제이다.

육각형에서 왜 거리가 2인지 한참 생각했는데, 팀원 중 한 명이 명석한 두뇌로 이유를 알려줬다.

 

각 삼각형들을 노드로 보고, 변이 맞닿은 곳은 이어준다면 트리 형태가 나오게 되는데, 모든 노드의 차수가 3 이하여야 하고, 트리의 지름이 가장 작아야 한다.

n이 짝수일 때는 아래와 같이 확장되는 것이 자명하다.

n이 홀수일 때가 약간 헷갈렸는데, 맨 처음 center를 기준으로 하는 3개의 방향 중 한 쪽 방향만 확장시키고 나머지는 놔두면 된다.

구현이 약간 말려서 여기서부터 패널티가 차곡차곡 쌓이기 시작했다.

 

 

L. What’s Mine is Mine

그냥 평범한 dp 문제이다. 각 day별로 해당 날짜에 일을 시작할 수 있는 상태일 때, 최대 price를 저장해놓으면 된다.

 

 

I. Thread Knots

스코어보드에서 I번이 쉽다는 소문을 듣고 찾아왔다.

문제는 그냥 명백한 binary search 문제였고, 바로 구현에 들어갔다.

high가 20억까지 나올 수 있다는 점을 간과해서 1틀을 해버렸다.

 

풀이는 "가장 가까운 점들의 거리가 t 이상이 되도록 놓을 수 있는지"에 대해 binary search하면 되고, 각 t를 테스트하는 것은 그냥 놓을 수 있는 내에서 최대한 앞쪽에 놓아보면 된다. 놓을 수 있는 knot의 갯수가 여러 개일 경우 가장 먼저 끝나는 knot에 우선적으로 놓아야 한다.

 

 

여기까지 정확히 130분이 소요되었는데, 이 이후로 한 문제도 풀지 못했다.

 

 

B. Gene Tree

tree의 모든 leaf pair 사이의 거리의 제곱의 합을 구하는 아주 간단한 문제이다.

이 문제랑 H번 문제를 고민하다가 4시간 10분쯤이 지날 때 풀이를 생각해냈는데, centroid decomposition을 구현해 본 적이 없어 구현할 자신이 없어 포기했다.

(모든 노드의 차수가 1, 3이라는 것이 문제에 있었는데, 문제를 읽은 팀원이 나한테 문제를 설명해줄 때 이거를 말을 안 해 주었다.. 확실히 이 정보가 있었으면 조금 더 자신감 있게 문제를 풀었을지도 모르겠다)

 

기본적인 풀이는 분할 정복이다.

 

특정 노드를 기준으로 트리를 2개로 나누고, 해당 정점에서의 거리를 각각

트리 1은 $d_1, d_2, d_3, ..., d_i$, 트리 2는 $e_1, e_2, e_3, ..., e_j$라 하자.

이 경우 해당 노드를 통과하는 경로들의 제곱의 합은 $(d_1 + e_1)^2 + (d_1 + e_2)^2 + ... + (d_i + e_j)^2$이 되는데, 전개할 경우 아주 깔끔한 식을 얻을 수 있다.

$j(d_1^2 + d_2^2 + ... + d_i^2) + i(e_1^2 + e_2^2 + ... + e_j^2) + 2 * (d_1 + d_2 + ... + d_i) * (e_1 + e_2 + ... + e_j)$

 

결국 우리가 알아야 할 것은 트리를 쪼갤 수 있는 적절한 점을 잡아, 해당 점에서 리프까지의 거리의 합, 거리의 제곱의 합, 리프의 갯수 3가지만 알면 된다. 이는 $O(n)$에 확인 가능하다.

 

다음으로 각 서브트리 안의 pair에 대해서 거리의 제곱의 합을 구해서 더해주면 되는데, 이는 재귀적으로 반복하면 된다.

 

총 복잡도를 $T(n)$이라 하면 익숙한 식인 $T(n) = 2 * T(n / 2) + O(n)$이라는 식이 나오는데, 해당 식을 만족하는 $T(n) = O(n \log{n})$임이 잘 알려져 있다.

 

적절한 centroid를 잡는 법을 몰라서 포기했었지만, 사실 worst하게 트리를 나누지만 않는다면 적당히만 잘라도 시간초과가 나지는 않는다. (가령 트리를 항상 절반으로 나누지 못하고 1:2가 되도록 나눈다고 해도, $log_2$가 $log_{1.5}$로 변하는 수준이다.)

 

 

H. Strike Zone

스트라이크와 볼의 정보가 들어왔을 때, 적당히 직사각형을 잡으면 안에 a개의 스트라이크와 b개의 볼이 들어올 것이다.

a * c1 - b * c2의 값을 최대화시키는 문제이다.

 

일단 좌표 압축을 통해 좌표를 줄이고, n이 1000이므로 $_{1000}C_2$개의 y값의 후보를 정하고, 적절한 전처리를 한 후 최대 부분 수열의 합(?) dp를 이용하면 복잡도 $O(n^3)$에 문제를 풀 수 있는 것을 발견했지만 어림도 없지.. 더 좋은 풀이는 찾지 못했다.

 

이 문제는 추후 rdd님께 여쭈어보니 금광이라는 문제가 있는데 이거랑 똑같다고 하셨다.

https://www.acmicpc.net/problem/10167

10167번: 금광

2014년 정올 중등부문제이다.

 

여기서 정올 준비를 하셨던 분들과의 격차를 새삼 느끼게 되었다. 정올 준비를 할 때 이런 문제들은 다 풀어보셨을 것이고, 기출이라 이번 대회에서도 쉽게 푸셨을 것 같은데 나는 아예 접해보지도 못했다.

단순히 문제에 대한 해법뿐만이 아니라, 이런 문제들을 많이 접하며 얻은 테크닉이나 내공의 상당한 격차가 느껴졌다.

 

 

D. Ladder Game

가장 쉬운 3문제 중 하나일 것으로 예상했는데, 가장 어려운 2문제 중 하나가 되었다는 말로 충격과 공포에 빠뜨린 문제..

 

흔히 알려진 사다리타기의 방식을 그대로 따르는데, 사다리타기의 결과로 생성되는 순열을 그대로 유지하며 사다리의 가로선 갯수를 최소화시키는 문제이다.

 

만약 같은 숫자를 교환하는 두 가로선이 존재한다면 (예컨대 1과 2를 바꾸고, 밑에서 1과 2를 또 바꾸는 경우) 두 선을 삭제해도 원래 순열에는 변화가 없다. 이러한 삭제를 계속 반복하면 풀린다. 왜 그런지는 나는 모른다.

 

 

마무리)

우리팀의 평소 실력대로면 5솔, 컨디션이 좋다면 6솔도 노려볼 만 했지만 결국 4솔이라는 다소 아쉬운 성적으로 마무리하게 되었다. 90팀 중 45등인데, 상위 50%에라도 들어서 다행이다. 석사 1학기차로서 마지막 ICPC여서 좋은 결과를 맺고 싶었는데, 아쉬움이 많이 남는 것은 사실이다.

사진을 하나도 안찍어서 빡겜중인 현장사진으로 대체

앞으로 DGIST에서 본선 진출을 할 수 있을지, 하더라도 좋은 성적을 낼지 미지수이긴 하지만.. 학교에 똑똑한 사람들도 많으니 앞으로도 좋은 결과가 있기를 바란다.

 

이제 인생에 남은 PS 대회는 내년 SCPC, (열릴지 기약이 없는) 카카오 코드 페스티벌, 내년 UCPC 정도일 듯 하다. 새삼 나이의 압박이 느껴지기 시작한다. 그래도 PS라는 것 자체가 굉장히 재미도 있고, 머리를 많이 쓰게 되는 장점도 있으니 평생 백준은 취미로라도 풀지 않을까 싶다.

코포는 계속 반복하다보면 조만간 오렌지는 달 수 있을 것 같은데, 레드는 평생 못 갈 것 같다.. ㅋㅋ 레드는 솔직히 너무 하드한 것 같고, 오렌지 정도를 계속 유지할 수 있으면 아주 만족스러울 것 같다.

 

내년 ICPC부터는 참가비 10만원이 생긴다고 한다. 정말 실력과 애정을 고루 갖춘 팀들만 참가하게 되지 않을까 싶다. 앞으로 ICPC를 밝혀줄 모든 사람들에게 응원의 박수를 보내고 싶다.

그리고 내년부터는 꼭 스코어보드를 공개하고 나서 수상을 하길~