SCPC 2018 1차(Round 1) 간략한 풀이

문제는 codeground.org에서 확인 가능합니다.

1. 버스 타기

$max( i-j | i > j, A_i - A_j <= K )$ 가 정답. upper_bound 함수를 이용해 $A_k$에 대해 $A_k ~ A_k + K$ 이하의 수가 몇 개 있는지를 세면 됨.

2. 회문인 수의 합

회문인 수가 10000 이하에서는 총 9+9+90+90 = 198개 있기 때문에 그냥 3중 for문 돌려서 $O(N^3)$으로 풀면 됨.($N$ = 회문인 수) 만약 회문인 수가 더 많아서 3중 for문을 돌리기 힘든 상황이었다면 binary search를 이용해 $O(NlgN+N^2)$에 해결할 수 있었음.

3. 우주정거장

degree가 2인 node들을 queue에 잡아넣고, queue가 빌 때 까지 queue에서 node를 뽑아, 그 node에 대해(그 node를 cur라고 하자.) 자신과 이웃한 두 node가 연결되어있는지 확인. 연결되어있다면 cur 노드는 없어져도 무방함. cur node를 지운 후 cur node와 이웃한 두 node를 A,B라고 할 때, A와 B에서 cur를 제거, 제거한 후에 degree가 2가 되었다면 queue에 삽입.

adjacency list를 set으로 가져가면 $O(NlgN)$에 수행 가능

4. 선형배치

N < 9일 때는 그냥 $O(N!)$으로 계산하면 되고, $N <= 100$일 때 우선 floyd algorithm로 각 점끼리의 거리를 모두 구한 뒤, 모든 점에 대해 그 점을 시작점으로 하고 일단 floyd 상의 거리를 작게 만드는 방법으로 점을 나열한 후에, 임의의 두 점을 swap해서 간선의 길이 합을 작게 할 수 있는 방법을 계속 찾아나가는 방식으로 해결하면 만점에 굉장히 근접한 점수를 받을 수 있음.(199.9) 일종의 Hill climbing method라고도 부름. 제출 횟수를 다 써서, 여기서 최적화를 더 해서 만점으로 갈 수 있는지, 아니면 만점을 위해서는 아예 다른 접근법이 필요한지는 잘 모르겠음.

5. Light to Stage

1. 전구를 달 수 있는 높이가 최대 $H$일 때, $L$개를 가지고 stage를 밝힐 수 있는지를 $O(M)$에 판단할 수 있음. -> 이 부분이 잘 캐치가 안될 수도 있는데, 글로 쓰기엔 좀 많이 복잡한 내용.. 직접 그림을 그려가면서 어떻게 각 line segment를 한 번에 뛰어넘을 수 있을까 고민해보면 좋을듯. 무대를 왼쪽부터 밝혀나간다고 할 때, 현재까지 밝힌 무대의 끝자락에서 $y = x$와 평행한 보조선을 긋어보는게 도움이 될 수도 있을듯.

2. H는 반드시 분모가 1이거나 2. 

1, 2 성질을 이용해 높이에 대한 parametric search를 하면 $O(Mlg(2*10^{12}))$에 계산 가능

이전 예선대회들 보다는 다소 쉽게 나온 것 같다. 본선 가서도 이정도만 할 수 있으면 더 바랄게 없겠다. 아 그리고 3, 4, 5번 모두 사소한 실수로 제출 횟수에서 손해를 봤다. 신중하게 코딩을 해야겠다.