2020 SCPC 2차 예선 후기

정말 오랜만에 하루종일 PS했다. 결과는 그렇게 맘에 들지는 않지만, 그래도 오랜만에 PS를 스릴있게 한 것 같다.다만 1년 전과 달리 실력이 별로 늘어난 느낌이 들지 않아서 좀 슬펐다. 1년 전에는 지금의 나는 SCPC예선쯤은 여유롭게 통과할 줄 알았는데, 역시 지난 1년간 PS 열심히 안한게 티난다..ㅋㅋㅋ 매우 아슬아슬한 점수인데 과연 본선 진출할 수 있을까?

1 - 실력 맞추기 (13:10 AC)

일단 두 개의 같은 길이의 배열 \(a_i\), \(b_j\)가 있고 1:1매칭을 해서 \(abs(a_i - b_j)\) 의 합을 최소화하는 문제인데, 대신 하나의 \(a_i\)를 임의의 숫자로 수정할 수 있는 문제이다. 기본적으로 아무 수정을 하지 않는다면 그냥 정렬하고 같은 인덱스끼리 매칭하면 되는데, 수정을 할 수 있으니까 좀 복잡해진다. 곰곰히 생각해보면 수정을 할 때 가로질러간 \(a\)의 원소들은 매칭되는 원소가 왼쪽 또는 오른쪽으로 shift된다고 생각하면 된다. 그러면 결국에는 한 간격을 골라서 그 간격의 맨 왼쪽 원소를 cost를 부과하지 않고 나머지 간격의 원소를 왼쪽으로 한 칸 shift해주거나, 같은 걸 오른쪽으로 바꿔서 하거나의 연산이 된다는 걸 알 수 있다. 이걸 maximum subarray 두 번으로 바꿔서 풀었다.

2 - 고구마 (11:39 AC)

각 위치의 누적합을 multiset안에 넣어놓고, 시작점을 고정한 후 제한을 넘어서지 않게 하는 가장 큰 누적합 값을 multiset안에서 찾는다. 제한 없는 버전의 maximum subarray 알고리즘인 kadane's algorithm이 끝점을 고정하는 알고리즘이라는 것에서 힌트를 얻었다.

3 - 아르바이트 (12:09 61점)

지난 예선 때 중간쯤 난이도 문제를 풀다가 안풀려서 멘탈이 터진 기억이 나서, 이번엔 중간 난이도 문제인 3번부터 공략하자! 하고 가장 먼저 본 문제다.하지만 결과적으로는 멘탈이 터진거랑 차이가 없는듯하다 처음에는 Q, K가 N과 똑같이 크다고 생각해서 살짝 당황했는데, Q, K가 작다는 걸 발견하고 그리 오래 걸리지 않고 Order Statistics Tree를 사용한 QKLogN풀이를 떠올렸다. 각 쿼리마다 K개의 원소를 OST에서 넣었다 빼고, 중간값은 find_by_order로 날먹하는 풀이이다. 빠르게 구현에 들어갔고, 이때까지만 해도 와 OST 날먹문제다! 와! 하고 좋아했지만 결과는 TLE로 0점. 이때까지만 해도 틀린 순 있어도 TLE는 말이 안돼는데? 거기다 0점? 섭테 채점이 잘 안된거 아닌가? 이라는 의문을 가지고 있어서 output flush 하기, fast io추가하기 등으로 한시간 남짓만에 채점기회를 5번 날려먹었다. 그런데 브루트포스를 짜서 스트레스 테스트를 해보니 잘못 짠 게 정말 많더라. 예를 들어서 n-k+1일 이후에 시작하는 부분합도 OST에 넣을려고 하거나...

몇번의 디버깅 후 61점을 맞았으나, 최종 결과는 여전히 TLE. 그 후 multiset두 개로 작은 부분/큰 부분을 따로 관리하는 식으로 중앙값을 관리하는 방식을 짜 보았는데, 벤치마킹 결과 2배 정도 빨라졌으나 여전히 TLE. 이때쯤 "T가 커서 QKLogN으로는 안풀리나?" 라고 생각했고 K를 떼는 알고리즘은 도저히 생각이 나지 않아서 그냥 반쯤 포기하고 4, 5번에 집중했는데, 알고 보니 그냥 multiset이 느린거였다.. 비슷한 알고리즘을 좌표압축+세그트리나 lazy delete가 있는 priority_queue으로 짜면 맞는다는 말을 주워들었다. 시간제한 좀 넉넉하게 주지 엉엉.. 아무튼 대회에서는 여기까지만 발전하고 마무리.

4 - 안전운전(19:44 41점)

41점 그 이후는 아무것도 떠오르지 않았고, 사실 3번과 5번에 집중하느라 별로 생각하고 싶지도 않았었다. 41점은 그냥 삼성코테처럼 빡구현을 하면 된다. :uwek:.. 머리가 나쁘면 몸이 고생한다..

5 - 삼각형의 거리(20:52!! 47점)

https://www.acmicpc.net/problem/17977 에 나오는 ICPC기출이라고 하는데, 나는 전혀 몰랐고 광란의 n^3 dp..? 그리디..? 로 맞았다.

우선 기하에는 정말 약해서 문제 전체를 맞는건 생각도 안했고, 5-1은 도형의 구체적인 모양에 의존하지 않고 n에만 의존한다는 건 감으로 찍었다. 

그림을 안그릴려고 설명할려니까 너무 귀찮다..아이패드 살까.. 대충 정n각형의 지름을 최소화하기 위해 일단 중간에 큰 삼각형 하나, 그 삼각형의 3변에 각각 a각형, b각형, c각형 (a+b+c - 3 = n)으로 나누고, a, b, c각형이 끝에서 중심에 오는걸 최대한 빠르게 하기 위해 이진트리처럼 다각형을 분해해주자. 구체적으로는 중심에 가까운 변에 큰 루트 삼각형 하나를 두고, 루트 삼각형의 나머지 두 변에는 또 다시 더 작은 다각형 두개가 남겨지는데 그걸 또 루트와 두 개의 children으로 분해하고.. 뭐 이런 식으로 분할 정복 비스무리한걸 하는 게 최적이라고 찍어 맞췄다. 나는 정육각형에서의 최소 지름 케이스를 그리면서 이러한 방법을 떠올렸고. 처음에는 구체적으로 분할정복 하는 방식에서 헛다리를 많이 짚었지만, 결국 대회 끝나기 한두시간 전쯤에 방향을 제대로 잡았다. 

 

위 사실을 깨달았으면 결국 가능한 a, b, c를 모두 순회하며, subproblem이 어떻게 나누어지는지 잘 분석해서 식을 써주면 된다. 이 때 a가 너무 크다면 a ->중심 -> b가 diameter가 아니라 a내부에서 도는 게 diameter가 될 수 있음에 주의하자.(여기서도 정말 많이 헤멨다..)

 

마지막에 한 20:30쯤에 맞는 코드를 내놓았는데, 좌표를 입력받는 코드를 주석처리한 것을 까먹고 제출한 탓에 0점을 맞았다. 난 그걸 모르고 아 dp식이 틀렸나보다.. 하고 체념하고 있었는데 끝의 끝에 미련이 가지않아 코드를 다시보니...!

교훈: 틀린 코드도 다시 보자(?)

 

 

끝! 더 열심히 해야지!