2024 SCPC (삼성 대학생 프로그래밍 경진대회) 1차 예선 후기

 

1. A보다 B가 좋아 (예측 S3) #문자열 #애드혹

모든 AA와 ABA를 지워주기 위해 사이에 B를 끼워넣어주면 된다. 증명: 어떤 구간 [l, r] 사이에 있는 A가 B보다 많다고 하자. 주장은 이 안에 적어도 1개의 AB 또는 ABA가 있다는 것이다. 이를 검증하기 위해 귀류법으로 저런 패턴이 없다고 가정하고, ABBABBA... 이렇게 써 보면 절대 A가 B보다 많아지지 않는다. 

 

2. 배달 (예측 S1) #정렬 #애드혹 #그리디

문제에서 주어진 식, |a-b|+|b-c|+|c-d|+|d-a|는 2*max(a,b,c,d) - 2*min(a,b,c,d)와 같다. 따라서 정렬 후 a, d를 가장 바깥쪽에서 골라주고 b, c를 가장 안쪽에서 골라주면 된다. 이를 N/4번 반복.

 

3. 보안망 점검 (예측 G3) #그래프이론 #그래프탐색 #조합론

degree가 3인 정점 2개를 찾으면 그 양옆으로 각각 길이 A와 B의 path가 생길 텐데 정답은 당연히 A(A-1)/2 + B(B-1)/2다. 조합론 부분이 너무 쉬워서 사실상 그래프 탐색이 다 하는 문제다. degree가 3인 정점을 찾는다는 아이디어가 없다면 판별에 어려움을 겪었을 수도 있겠다.

 

4. 딱 맞게 (예측 P4~P3) #정렬 #투포인터 #세그먼트트리/트리맵 #그리디

다음 두 문제를 절묘하게 섞은 데다가 세그트리까지 부은 진짜 웰메이드 문제.

2470 두 용액 (이분탐색 말고 투포인터로 풀기)

1727 커플 만들기

2470에서 볼 수 있듯이 두 배열 l1, l2가 주어졌을 때 (전처리로 정렬했다고 하자) |l1[i] - l2[j]| <= L이 되게 하면서 max(|l1[i] - l2[j]|)를 구하는 문제를 O(N)에 풀 수 있다. 그러면 만약 i, j 쌍이 정해졌고 둘 사이에 연결이 있다는 걸 아는 상태라면, 나머지 원소들을 어떻게 짝지어야 모든 원소 쌍의 차이의 최댓값이 최소가 되게 할 수 있을까? 1727을 풀면 알 수 있지만 정답은 그냥 l1[i], l2[j]를 제외하고 l1의 k번째로 작은 원소와 l2의 k번째로 작은 원소를 잇는 것이다. 따라서 |l1[i] - l2[j]|의 최댓값을 주는 i, j가 정해졌다고 가정하면, 크기 n-1의 set이 존재해서 |l1[i] - l2[j]|은 이 set의 최대 원소 이상임을 검증해야 i, j가 정말로 최댓값을 주는 인덱스라는 사실을 알 수 있을 것이다. i, j 후보는 O(N)개가 존재하며 투 포인터로 구할 수 있고, 포인터가 한 칸 움직일 때마다 set에서 원소 하나가 빠지고 원소 하나가 새로 들어온다. 원소가 빠지거나 들어올 때마다 그 set에 든 원소의 최댓값을 알고 싶은데 이것은 max segment tree를 사용하거나, 임의 원소 pop이 가능한 PQ를 사용하면 된다. (지금 생각하니까 treeset 구현이 오히려 더 쉬웠을 듯) (수정: treeset 쓰면 시간 초과가 난다는 제보가 들어왔다. 생각해보면 maxseg 썼을 때도 1.3초 걸렸으니 treeset은 더 걸릴 듯하다.) 따라서 포인터 움직임을 O(log N)에 구현할 수 있다.

 

5. 스퀘어 (예측 P2) #mo's

걍 mo's 표준스러운 문제라 코멘트가 별로 없다. mo's 문제는 mo's라는 티가 너무 잘 나는 것 같다. 수열 업데이트 없음, 구간 쿼리, 포인터를 1씩 움직이는 게 쉬움. 심지어 N을 50000으로 줘서 시간복잡도 O(NsqrtN)이 허용된다는 게 너무 잘 보였다.

 

어제 필라테스 하고 와서 몸살이 났다. 근육통이야 당연히 있을 수 있는데 왜 두통까지 같이 오는지... 이 상태에서 1차 예선 풀려니까 죽을 맛이긴 하더라.