SCPC 2018 1차예선

<SCPC란?>

SCPC는 삼성에서 주최하는 대학생 대회로, 상금이 빵빵하기로 유명하다. (스택메모리 1MB밖에 안 주기로도 유명하다 UPD(20.12): 이젠 스택메모리제한 따로 없다)

1차 예선, 2차 예선을 온라인으로 치른 뒤 본선을 오프라인 대회로 치른다.

<요약>

올해 1차 예선은 배점이 100 / 100 / 150 / 200 / 250점으로, 4번째 문제를 제외한 나머지 문제는 평범한 알고리즘 문제, 4번째 문제가 Optimization Problem (??)이 나왔다. 요즘 유행인가...

나는 모든 문제에서 만점을 받았다! 예선 특별상 같은 거 안주나...

<문제별 후기>

1. 버스 타기

n(<=200000)개의 숫자가 있을 때(같을 수도 있음) 이들을 최소 갯수의 집합으로 분할할 건데, 같은 집합에 차이가 k 이하인 두 수가 있으면 안 된다.

간단한 greedy 전략으로, 매번 아직 집합에 들어가지 않은 수들 중에 가장 작은 것부터 시작해서 차이가 k 초과인 것 중 가장 작은 걸 고르고, 또 거기서 차이가 k 초과인 것 중 가장 작은 걸 고르고.... 하는 식으로 집합을 골라나가면 될 거 같다. set 자료구조를 사용하면 간단하게 이를 처리할 수 있다. 시간복잡도는 TC당 O(nlogn).

2. 회문인 수의 합

n(<=10000)이 최대 3개의 회문인 숫자의 합으로 표현되는지 여부를 판단하고, 표현된다면 그 방법 중 하나를 구하는 문제이다.

10000 이하의 회문인 수를 미리 다 구해놓고 그 갯수를 C라 하자. C는 100 언저리의 수이다. 따라서 O(C^3)으로 3개를 골라 봐서 그 합이 n이 되는 게 있으면 출력하면 된다.

사실 나는 O(C^2logC)를 짜긴 했다...

3. 우주정거장

정점 n(<=200000)개, 간선 m(<=400000)개짜리 그래프가 있는데, degree가 2인 정점 중에 그 정점과 이어진 두 개의 정점 사이에도 간선이 있으면 그 정점을 제거할 수 있다. 이 연산을 반복적으로 적용해서 정점 수를 최소화하는 문제이다.

degree가 2인 정점을 제거하는 순서는 상관이 없다. (제거하는 정점들끼리 순서 관계가 아마 DAG일 거다. 즉 'a를 먼저 제거하면 b를 제거 못 하고 b를 먼저 제거하면 a도 제거할 수 있는' 경우 같은 게 없다) 따라서 그냥 매번 degree가 2인 정점을 아무거나 찾아서 그게 제거될 수 있으면 제거하고, 아니면 그냥 무시하면 된다. 간선을 들고 있는 set과 각 정점의 degree를 들고 있는 set을 사용하면 간단하게 구현할 수 있다. 시간 복잡도는 TC당 O(nlogn).

4. 선형배치

정점 n(<=100), 간선 m(<=1000)개인 그래프의 정점들을 수직선 상의 0 ~ (n-1)까지의 정수 좌표에 배열하는데, 이 때 간선들의 길이의 합을 최소화하는 문제이다.

채점 방식을 보아하니 최적화 문제이다. (polynomial time solution이 존재할 수도 있는데, 나는 일단 잘 모르겠다) 이런 종류의 문제에 가장 잘 먹히는 방식 중 하나가 Simulated Annealing이라는 방식인데, '온도'라는 변수를 iteration에 따라 일정 비율씩 줄여 가면서, 어떤 상태에서 약간씩 변화를 줘 가면서 평가함수(이 문제에서는 간선들의 길이의 합이 되겠다)의 변화값을 delta라 할 때 min(1, exp(-delta / temperature))의 확률로 새로운 상태로 넘어가는 식이다. (설명을 간단하게 해 놔서 이해가 안 될 수 있는데, 자세한 정보는 google을 참고하길 바란다)

우선 각 정점에서 시작하는 dfs preorder numbering으로 위치를 매겨봐서 그 중 가장 좋은 것에서 시작한 뒤, 매 iteration마다 랜덤한 두 정점 위치 바꾸기를 TC당 150만번 iteration, 초기 온도 (n-1)*10000, 온도 감소비율 0.999988로 설정해서 했더니 만점이 떴다. 이런 문제를 왜 낸 건지는 잘 모르겠다. 본선에도 내겠다는 의지인가?

5. Lights to stage

기울기 +1, -1인 직선들로 이루어진 선분들의 집합 위 점 L(<=200000)개에 전구를 놓아서 아래쪽으로 좌우 45도 범위를 비춘다고 할 때, y좌표가 0인 길이 N(<=10억)짜리 무대를 모두 비출 때 가장 높은 전구의 높이의 최솟값을 구하는 문제이다. 이상하게도 y좌표 범위는 0에서 1조 사이이다...

일단 전구를 반정수 (정수/2) 좌표에만 두어도 최적해가 됨을 짐작할 수 있다. 따라서, 입력된 N값과 좌표값에 모두 2를 곱해서 정수 점에만 전구를 놓는 것을 고려한 뒤 나중에 2로 나누어서 출력하면 된다. 이제, parametric search로 가능한 최소 높이를 구해 보자.

전구를 높이 h 이하의 위치에만 설치할 수 있다고 가정하면, 원래 선분 집합의 일부분만 사용이 가능하게 되는데, 각 선분별로 그 선분 상에 전구를 놓는다면 가장 높은 위치에 하나만 놓는 것이 최적이기 때문에, 그 선분 상에 전구를 놓았을 때 최대 어느 구간을 덮을 수 있는지를 간단한 수식으로 구할 수 있다. 그 다음에, 구한 구간들 중 L개 이하만을 사용해 0 ~ N 사이의 모든 x좌표가 덮이는지를 검사하면 되므로, greedy 전략으로 좌표 0에서부터 시작해 매번 (현재 좌표를 포함하는 구간) 중 (오른쪽 끝이 가장 오른쪽에 있는 구간)을 택하는 방식으로 진행할 것이다. 이를 위해서는, (좌표압축을 한 상태에서) 각 구간을 [s[i], e[i]]라 하면 prefix max 배열의 s[i] 칸에 e[i]를 갱신해준 뒤 좌표압축 후 0이 가는 위치부터 시작해 (t라 하자) t = p[t] 연산을 L번 해 주어서 마지막에 N을 넘어가는지를 보면 된다. 시간복잡도는 O(nlognlog(10억))으로, (log(1조)가 아닌 이유는 y좌표가 N보다 큰 선분이 하나라도 있으면 거기에 하나 딱 놓으면 무조건 무대가 전부 비춰지기 때문이다) 의도한 풀이에서 로그가 하나 덜 붙는지는 모르겠는데 나는 시간이 좀 빡셌다.

2차 예선도 이렇게 잘 보면 좋겠당 ㅎㅎ