SCPC 2020 2차 예선 후기

멘탈이 갈려나가고 이래저래 바빠서 후기를 계속 미루고 있었다.

역대급으로 망하고 힘들었던 대회인 듯... 오전 9시 - 오후 9시라서 힘든것도 60% 정도 있지만, 꼭 그것만은 아니다.

3번 문제의 Whining이 역대급이므로 나머지 문제에서의 Whining을 줄이고 (3번 제외) 건조한 느낌으로 써보려고 한다. 다만, 내가 문제를 푸는 과정을 최대한 그대로 따라갈 생각이다.

즉, 한번에 바로 풀이로 접근하기보다는 '이런 과정으로 생각해 봤다' 라는 느낌.

---

1번 : 실력 맞추기

문제 설명 : $n \leq 300,000$ 명의 팀원이 있는 두 팀이 있고, 이들에게 각각 실력값 $A_i$ 와 $B_i$가 주어져 있다.

이들을 Matching한다. $A_i$ 를 $B_{f(i)}$ 에 매칭했을 때, $\sum_i \abs{A_i - B_{f(i)}}$ 의 값을 최소화하는 것이 목표.

단, A팀에서 한명을 골라 실력을 임의로 바꿀 수 있다.

 

풀이 : 이 문제를 푸는 핵심 관찰은 다음과 같다.

- 먼저, '사람 바꾸기' 가 없다면, 최적해는 양쪽을 정렬한 다음 정렬 순서대로 매칭하는 방법이다. exchange argument가 될 것 같다.

- 사람 바꾸기는 사실 사람 한명씩을 빼는 것으로 충분하다. $A_i$ 를 빼기로 했다면, 이 $A_i$를 $B$ 중 하나의 값으로 바꾸면 그 사람도 없어지는 것과 같아지기 때문이다.

 

이제, Dynamic Programming 풀이를 생각해 보자. 간단한 풀이는 $D_{i, j}$ 를 $A_i$ 와 $B_j$를 매칭할 때의 최적값으로 정의하는 것이다. 이때 정렬 순서대로 매칭할 것이므로, 미리 정렬해 놓으면 $n \times n$ dp 테이블을 좌상에서 우하 방향으로 채우면서 나아갈 수 있을 것이다. dp[3][3] 이라면 양쪽에서 3명씩을 매칭한 것이다.

 

이 풀이는 당연하지만 그대로 쓸 수 없다. 우리에게는 $O(n^2)$ 시간도 메모리도 없기 때문이다. 대신에, 위 DP 테이블을 직접 채워 본다면, dp[1][5] 같은 칸들은 어차피 쓸 수 없음을 관찰하게 된다. 양쪽에서 최대 한명까지 빼서 없앨 수 있기 때문에, dp[2][3] 은 가능하지만 dp[2][4] 나 dp[4][2] 는 불가능하다. 따라서, DP 테이블의 $(i, i)$ 대각선을 기준으로 위아래 한줄씩만 봐도 된다.

 

다만, $(i, i)$ 대각선의 경우, '아무도 빼지 않은 경우' 와 '양쪽에서 한명씩을 뺀 경우' 를 구분해야 한다. 왜냐면, $(3, 3)$ 을 예로 들 때, 아무도 빼지 않고 $(3, 3)$에 왔다면 $(3, 4)$ 로 갈 수 있지만, 양쪽에서 한명을 이미 빼면서 $(3, 3)$ 에 왔다면 그렇게 할 수 없기 때문이다. 

 

따라서 필요한 대각선은 4줄이다. 아무도 빼지 않은 경우, A에서 한명 뺀 경우, B에서 한명 뺀 경우, 양쪽에서 한명씩 뺀 경우. 이러면 $O(4n)$ 이므로 $O(n)$ 시간에 DP를 돌릴 수있다.

 

여담 : 많은 사람들이 비슷하게 풀었지만 대부분 $n^2$ dp 없이 그냥 바로 '뺀 상태' 를 00, 01, 10, 11로 인코딩한다고 풀이를 적었다. 생각의 과정이 비슷한지, 내가 DP를 못 풀어서 저런게 잘 안 보이는지는 궁금하다.

---

2번 : 고구마

문제 설명 : 수열이 주어지고, 이들 중 $i$ 부터 $j$ 까지의 부분구간합을 최대화한다. 단, 합이 $M$을 넘지 않게.

풀이 : Well-Known 이라고 생각한다. $M$ 조건이 없으면 Kadane's Algorithm으로 $O(n)$ 에 풀 수 있다.

합이 $M$ 을 넘지 않아야 하고, $i$ 부터 $j$ 까지의 부분구간합은 부분합배열에서 $S_j - S_{i-1}$ 임을 관찰하자. 내 앞의 모든 $S_i$ 값을 multiset에 넣어 놓고, $S_j$ 를 만나면, $S_j - M$ 에 가까운 값을 lower_bound 같은 함수로 멀티셋에 쿼리하면 $O(n \log n)$ 에 풀 수 있다. 1번보다 쉽다고 생각한다. 

---

3번 : 맨 뒤로 미룬다. 하고싶은말이 많다.

4번 : 모름. 구현도 빡세고 풀이도 어렵고... 2019 드론에 이어 또 구간을 이상하게 주는 입력이 주어졌다. 나같은 사람은 입력을 받는 것만으로도 그날 하고싶은 일일 코딩 허용량을 초과한다.

---

5번 : 삼각형의 거리

문제 설명 : 다각형이 주어진다. 이를 삼각화하되, 삼각화한 다음 Dual graph를 생각하자. (Dual graph 란, 기존의 그래프에서, 면마다 정점을 두고, 이웃한 면끼리 간선을 둔 그래프) Dual graph의 Diameter가 최대화되게 하고자 한다. (단, 바깥면은 생각하지 않는다)

 

풀이 : 서브태스크인 '볼록다각형' 의 경우, ICPC 2019 Regional에 출제된 [Triangulation]과 같다. 당시 리저널에 진출하지 못하고 온라인 미러에 참여했었고, DHdroid가 생각 거의 했으니 잠깐 화장실좀 갔다가 구현한다고 말하고 나간 사이에 내가 도대체 무슨 문제인가 하고 슬쩍 보다가 맞았던 (...) 문제였기 때문에 기억이 났다. 

오목다각형의 경우, 다각형의 대각선을 이용하는 DP 풀이를 생각할 수 있다. 이 풀이는 정확히 이 문제를 푸는 논문의 풀이로, $O(n^3 \log n)$ 시간에 해결할 수 있다. 당연히 이런걸 내가 코딩할수 있을리가 없었다. ㅋㅋ;;;

솔직히 편안한 분위기에서 모든 걸 내려놓고 저 논문을 보며 코딩했어도 될까 말까인데, 대회 시간 중에 구현을 생각하고, 오목다각형의 대각선판정같은 복잡도의 구현을 실수없이 수행하는것은 내게는 너무 먼 이야기이다. 

---

3번 : 아르바이트

문제 설명 : $N \leq 200,000$의 배열에서, $Q \leq 2,000$번 쿼리를 수행할 것이다. 이때 쿼리란, 다음과 같다.

- 특정 인덱스의 값을 바꾼다.

- 바꾼 후, $N$ 크기의 배열에서, $K \leq 200$ 짜리 부분배열의 합들을 생각하자. $N-K+1$ 개의 부분 배열 합이 존재할 것이다. 이들 중, 중간값을 출력한다.

 

생각 : 인덱스의 값을 바꾸지 말고, 그냥 '부분배열의 합'들을 모조리 관리하자. 특정 인덱스의 값을 바꾸면 $K$개의 값이 바뀌어야 한다는 사실을 쉽게 관찰할 수 있다. 간단히 말해서, 한번에 $K$개씩 업데이트 연산이 있을 때, $Q$ 번 중간값을 구하는 문제.

배열이 변화하는데 그와중에 중간값을 구하는 문제는 매우 Standard하다. 다양한 solution이 있는데,

1. Order statistics tree 같은 자료구조를 쓰면 간단하다.

2. Segment Tree 같은 자료구조가 있으면, kth number query를 처리할 수 있음이 알려져 있다.

3. multiset 두개를 이용하자. set 하나는 전체에서 절반씩을 점유할 것이고 각각을 big 과 small 이라고 부르자. big의 최소값이 small의 최대값보다 크거나 같도록 유지한다. 이때, 값을 빼거나 넣는 연산은, 어디에서 뺴는지 확인하고 어디에 넣는지 확인한 다음, 실제로 넣고 빼는 연산을 수행하고, set 두개의 크기가 맞도록 small의 최대를 big에 넣거나, big의 최소를 small에 넣으면서 개수를 맞추면 된다. 

4. multiset 하나에서, 중간값을 한번 찾은 다음, insert나 delete가 일어날 때 중간값을 가리키는 iterator를 좌우로 약간씩 움직여 주면 된다. 구현하기가 매우 빡세고 예외처리가 많다. 

5. 3번의 풀이는 최소와 최대만을 필요로 하므로 priority queue 등 heap 기반의 자료구조를 쓸 수 있다. 다만 heap은 삭제 연산이 어려우므로, 이를 직접 구현해야 한다.

 

내가 고통받은 과정

잘 보면, $QK$ 번의 업데이트가 있다. QK는 400,000 이다. 타겟 복잡도는 $O(QK \log n)$ 내지는 그 비슷한 뭔가라고 생각했다.

다만, 테스트 케이스가 최대 100개이므로 최대 4천만 번의 업데이트가 있음에 유의하여야 한다. 제한 시간이 몇초인지는 기억이 안나지만 (6초라고 기억한다) 이정도면 로그 시간에 돌기 매우 빡세다. 1번은 당연히 안 될것 같았지만 부분점수를 받기 위해 내 봤고, 2번을 구현하기 싫어서 3번을 쓰려고 했다. (2번이 더 빠를것이라는 생각이 들지 않았다) 다만 multiset을 사용해야 하는데 multiset이 대단히 무거워서 4천만번의 로그시간 업데이트가 가능한지 의심스러웠다. 실제로는 4천만번이 아니라, '넣고 빼는 연산' 은 적어도 그 2배이며, 멀티셋 크기 바로잡기에 드는 시간을 고려하면 1억번 정도는 감수해야 한다.

삼성 SCPC 대회는 서브태스크에 대한 부분점수를 일반적인 방법으로 각각 돌려보고 부여하는 것이 아니라, 시간초과가 날때까지 돌려보고 죽으면 그때까지 출력된 결과가 몇번째 결과까지 맞았는지를 확인한다. 그렇기 때문에, 시간초과가 나는 코드에서 flush 할 책임이 나한테 있다. 그러나 이렇게 상수가 조이는 문제라면 나는 사실 flush 하는 시간도 만만치 않을 것이라는 생각에, flush를 했다 안했다 바꿔가면서 제출해 보았다. 이게 그렇게 큰 실수일 줄은 몰랐다.

 

대회 시작후 약 6시간 시점에, 멘탈이 완전히 탈주하고, 본선에 못 나갈지도 모른다는 공포가 엄습하면서 (...) 유리멘탈 특성이 발동해서 능지가 박살났다. 그와중에 3번을 포기하고 4번을 작성하려고 시도했으니 되도 않는 게 당연하다. 이때까지 로컬에서 테스트로 쓰고 있었던 brute force 코드가 틀린 것을 발견했다.

 

3시부터 6시까지 3시간 동안 멘탈을 놓은 채 많은 생각을 했다. Lazy propagation 같은 기법을 이용해서 K를 복잡도에서 떼는, $Q \log n$ 풀이가 정해이고 내가 어거지를 쓰는게 아닌가? 하는 생각을 잠깐 했다. 생각해보면 그런 경우 100개의 테스트케이스가 있음에도 6초가 제한시간인게 납득이 가기 시작했다. 그런데 로컬에서 내 코드는 max test에서도 십몇초 내외었기 때문에, 희망을 놓지 못하고 매달렸다. ㅋㅋ;;; 이때 침착하게 모든 솔루션의 상수를 비교하기 시작했어야 했다.

이때 3시간 동안 쓰레기를 제출하며 제출 횟수를 날려 먹었다.

 

저녁을 먹고 3시간 정도 시간이 남았을 때 선택한 것은 결과적으로 세그트리가 set보다 빠를 것 같다는 확신이었다. 세그트리는 업데이트를 비교적 빨리 할 수 있는데, set의 크기를 마구 조절하면서 시간을 낭비하지 않기 때문이다. 다만 세그트리 같은걸 쓰려면, $O(NK)$ 칸의 세그트리를 만들어야 한다. 잘 보면 $NK$는 4천만으로, 4천만 칸의 세그트리를 쓰는 경우는 듣도 보도 못했다. 그러나 동시에 쓰는 칸은 20만 칸밖에 없기 때문에, Dynamic Segment Tree를 쓸 수 있다. 4천만의 로그는 25이지만 20만의 로그는 17 정도이므로, 다이나믹해도 느리지 않을 것이라고 생각한 것도 있다. 생전 처음으로 다이나믹 세그먼트 트리를 코딩했지만, 세그먼트 트리를 이해하고 있다면 코딩이 그렇게까지 어렵지는 않고, 솔직히 말하자면 오히려 더 자연스러운 측면이 있다.

3시부터 6시까지 3시간동안 쓰레기를 제출하며 제출횟수를 모두 허비했기 때문에, 제출 횟수는 단 한 번 남아 있었고, 내가 할수있는 모든 최적화를 끝냈을 때 시간이 8시가 좀 넘어 있었다. 이걸 제출하고 나면 더이상 할수있는게 없으므로 그 frustration을 견딜 자신이 없어서 8시 58분에 마지막 코드를 제출했고 시간 초과를 받았다.

 

바로 욕하면서 대회를 마무리할 수 있었다. ㅋㅋ;;

 

여담 (고통받은 과정 II): 대회가 끝나고 나랑 같이 시간초과를 받았으나 나보다 부분 점수를 더 긁은 dlwocks31 등과 문제를 토론했다. Gyuni님이 (나는 직접 들은게 아니라 잘 모르겠지만) $O(q \log^2 (n + qk))$ 같은 풀이를 dlwocks31에게 알려줬다고 하던데, 솔직히 정해가 저거라면 나는 아무런 불만도 없고 조용히 머리박을수 있을것 같았다.

 

UPD : 작성 완료 2분 만에 dlwocks31이 알려줬는데 그냥 비재귀 세그를 쓰는 풀이고, $nk$ 칸이 아닌 $n + qk$ 칸 메모리를 잡으면 된다고 한다. $n+qk$ 로 된다는 생각을 못했으므로 여전히 머리는 박을 수 있다!

 

그런데 NK (4천만) 칸의 펜윅 트리나, 심지어는 다이나믹 세그를 포인터가 아닌 인덱스를 쓰는 구현 등이 통과했다는 소식을 들었다.

결과적으로 나는,

1. 61점의 부분점수를 받을 수 있는 풀이를 시작 10분 만에 코딩했으나 flush 문제로 아무것도 받지 못했고

2. 펜윅 트리 4천만칸이 잡히는지를 모르고 개삽질을 했으며

3. 다이나믹 세그먼트 트리는 가능한 구현이지만 뭔가 실수해서 (잘 모르겠지만, 최대한 Dynamic하게 하기 위해 node를 삭제하는데 그게 오래 걸리는 것으로 보인다 틀렸다.

4. dlwocks31에 의하면 로컬에서 본인의 61점 구현체와 비교했을 때 내 Dynamic Segment Tree는 stress test를 통과하며, 2배 정도 빠르다고 한다. 그런데 왜 마지막에도 61점을 받지 못했는지는 결국 둘다 찾지 못했다. flush에 대한 규칙을 이해하지 못했다고 생각한다.

---

12시간이나 24시간 같은 비인간적인 시간의 대회임에도 최선을 다하려고 노력했으나 능지가 부족해서 실패했다고 생각하기로 했다. 대회가 끝나고 이렇게 Frustrating 했던것은 2019 SNUPC가 지금까지 최고라고 생각했는데, 2020 SCPC 2차예선은 그보다 10억 7배정도 심했기 때문에 그 과정을 블로그에 박제해놓고 삶이 지나치게 행복할 때마다 보려고 한다. ㅋㅋ;;