2023 경인지역 6개 대학 연합 프로그래밍 경시대회 shake! Open Contest 후기

요새 계속 스트릭 유지를 위해서 별로 어렵지 않는 문제들만 풀어보다가 CP 실력도 죽은게 아닌가 싶기도 하고 마침 시간도 나서 2023년 shake! 대회에 참가해보았습니다. 아레나 등록하고 참가해보았는데, 제가 여태까지 해본 아레나 중에서 제일 어려웠던 것 같습니다. 특히나 난이도 순서대로 배치된게 아니라 랜덤으로 배치되어서 어느 문제가 쉬운지 파악하는데 좀 애를 먹었던 것 같습니다. (그래서 그냥 스코어보드 보고 몰리는데로 따라갔긴 했습니다.) 이제부터 시간 순대로 어떤 문제들을 풀어보았는지 후기를 남기도록 하겠습니다.

 

2023 경인지역 6개 대학 연합 프로그래밍 경시대회 shake! 결과입니다. 아레나에서는 총 13등으로 마무리, 오픈컨에서는 총 21등으로 마무리 했었습니다.

 

1. C번 : 또 수열 문제야 (+1)

 

Ad-hoc + Constructive 문제였습니다.

 

일단 스코어보드에서 제일 빠르게 정답이 나와서 별 생각없이 '제곱수만 다 넣어도 괜찮지 않을까?'라고 생각하여 상큼하게 1 WA를 받고 시작했습니다.

 

이후에 '소수에서 ab % (a+b) == 0은 나올 수 없겠다.' 라 판단하여 N개의 소수들을 순서대로 출력하여 AC를 받았습니다.

그런데, 나중에 디스코드방에서 그냥 홀수들만 출력하면 되는 문제였다길래 오버킬을 했구나 싶었습니다.

 

*여담으로 소수에서 ab % (a+b) == 0 이 나올수 없다는 이유는 다음과 같았습니다. a,b는 서로소이며 소수입니다. 따라서 소인수분해 결과에 따라서 ab는 약수가 1, a, b, ab 밖에 없습니다. 그 와중에, a > 1, b > 1 이므로 ab = a+b인 경우만 조심하면 되는데, b로 나눠보면 a = a/b+1 꼴이 됩니다. 그런데, a는 자연수이고, a와 b가 서로소인 관계로 a/b는 자연수가 아닌 유리수가 되므로, ab = a+b 인 a,b는 존재할 수 없습니다.

 

2. I번 : 올라올라 (+1)

 

Binary Search + Monotone Queue로 풀었긴 했습니다.

 

최소 k를 찾는 문제였어서 Binary Search가 빠르게 떠올랐고, 이후에 특정한 크기의 구간별로 최댓값을 찾는 문제라서 Multi-set 아니면 필요시 Monotone Queue 테크닉도 써야한다는 판단을 하였습니다.

 

그런데 사람들이 빠르게 풀었으니 Multi-set을 사용하는 풀이도 되겠지라는 마음에 써봤는데 1 TLE가 났어서, 급하게 예전에 구현해둔 Monotone Queue 테크닉 코드를 가져와서 고쳐서 AC를 받았습니다. 

 

정해는 Greedy 아니면 Stack이라고 하던데 잘 모르겠습니다. (Greedy는 대강 코드를 보니 Two-pointer랑 섞어서 좀 더 쉽게 풀 수 있었나 보네요.)

 

3. D번 : 모비스터디 (+0)

 

Dijkstra + 역추적으로 풀었습니다.

 

일단 문제에서 지시한대로 A에서 각 노드별로의 최단 거리를 구했습니다.

 

이후에 B부터 순서대로 현재 보고 있는 노드가 n이라면 dist[n] = dist[k] + cost[k]를 만족하는 k 노드를 다음에 보도록 BFS를 하였습니다. (이 과정 자체가 역추적이기도 하지요.)

 

BFS를 하는 과정에서 탐색한 모든 노드들을 set에 담아두어 나중에 오름차순으로 출력하니 AC를 받았습니다.

 

4. B번 : 실 전화기 (+2)

 

수학 문제였습니다.

 

C를 풀고 손을 댔던 문제였는데, 그림을 몇 개 그리면서 별 생각없이 'N, K가 서로소가 아니면 사이클이 생기므로 0이 답이고 아니면 min(N*(K-1), N*(N-K-1))이 답일 것이다'라는 판단을 하여 그렇게 짰습니다. 당연히 1 WA를 정립하였습니다.

 

그러다가 D, I번이 스코어보드에 많이 AC를 받은게 보여서 두 문제를 풀고 다시 와서 이번에는 'N%min(K, N-K) == 0인 경우에만 답이 0이겠구나' 생각해서 그렇게 고치고 제출하니 2 WA도 적립하였습니다.

 

그래서 왜 틀렸는 가 싶어서 N = 10, K = 4인 예제를 그려보았는데, N과 K를 최대공약수로 나누어주고 min(N*(K-1), N*(N-K-1))을 구해야 하는 것을 알아서 고쳐서 AC를 받았습니다.

 

5. G번 : 관광 상품 (+0)

Ad-hoc 문제가 아니었나 싶습니다.

 

문제를 보다가 '4개를 보았을 때 최대가 나온다면 2개로 보았을 때도 최대가 나올 수 있을 것이고, 5개를 보았을 때 최대가 나온다면 3개로 보았을 때도 최대가 나오지 않을까?'라는 생각을 해서 구현했는데 얻어 결렸습니다.

 

나중에 디스코드 방에서 알아보니 꽤 유명한 웰노운 문제였다고 합니다. 이건 제가 정해랑 증명을 이해하고 한 번 블로그에다가 정리해봐야 할 것 같습니다.

 

6. H번 : 대역폭 관리 (+1)

 

Heavy-Light Decomposition + Lazy Segment Tree로 풀었습니다.

 

일단 문제에서 제일 필요한 건 사실상 경로에 속한 모든 노드들에 대해서 값을 업데이트를 해주어야 했는데,

이걸 어떻게 구간으로 치환이 가능하다면 Lazy Segment Tree로 구할 수 있겠다는 생각이 들었습니다. 이게 가능하다면 해당 예약을 받으면 문제가 되는지 안 되는지도 업데이트가 될 구간에 대해서 minimum query를 날린 결과가 w보다 작은지 안 작은지로 판단이 될 테니 경로를 구간으로 치환만 해줄 수 있는 방법을 찾으면 되겠다는 생각이 들었습니다.

 

그래서 경로들을 어떻게 구간으로 바꿀까 생각했을 때 처음에는 Euler Tour Trick을 생각해보았는데, 제가 생각한 Euler Tour Trick을 활용한 해에서는 문제점들이 존재했습니다. 그래서 다른 방법들을 찾아 인터넷을 뒤져보니 Heavy-Light Decomposition을 활용하면 되겠다는 아이디어를 얻었습니다.

 

Heavy-Light Decomposition은 Heavy한 간선들을 한 그룹으로 엮어서 경로상에 있는 노드들이 같은 그룹이라면 O(logN)만에 업데이트 할 수 있었습니다. 알고리즘 전체 원리를 제대로 파악은 하지 못했긴 했지만 대강 Square-root Decomposition 같이 구간들을 특정 크기만큼씩 쪼개어 시간복잡도를 줄이고, 또한 Smaller-To-Larger와 비슷한 원리로 light한 간선들을 탔을 때 크기가 2배 이상씩 늘어나니 O((logN)^2)만에 구간 업데이트가 가능하다고 파악했습니다. 

 

그래서 Heavy-Light Decomposition을 구현한 글을 참고해서 Minimum Query를 날릴 수 있는 Lazy Segment Tree를 구현했고, 이를 HLD 코드와 잘 작동하도록 다듬어서 제출해보니 구현 실수해서 WA를 받았습니다. 이후에 디버깅해서 다시 제출해보니 AC를 받았습니다. 처음으로 HLD 문제를 이렇게 풀어보게 되어 감격스러웠으나... 정해는 LCA라고 합니다. (LCA 문제라고도 생각은 해보긴 했는데... 어떻게 풀어야 할지는 아무래도 아이디어가 안 떠오르네요...)

 

여기까지가 이번 대회에서 제가 푼 문제들이었습니다.

이외에도 못 푼 문제들에 대해서도 대강 후기를 남겨보자면...

 

A번 : 

일단 이 문제를 보자마자 BOJ 27280 이기적인 목봉체조 (Easy) 문제가 생각났습니다.

 

O(M^2)만에 [k..j]에서의 제일 떨어진 두 점의 거리들을 모두 전처리해서 구할 수 있었고 이제 DP[N][K] = max(DP[N-1][j] + cost[j][k], DP[N][K])를 최적화하여 풀면 될텐데... 저 DP식을 어떻게 최적화 해야할지 몰라서 못 풀었습니다.

 

짧은 식견으로나마 대충 예상해보면 Segment Tree를 활용해서 max 쿼리를 어떻게 날려서 저 DP 테이블을 모두 구하는데 O(NMlogM)만에 구할 수 있었지 않았을까 생각해봅니다. (마치 BOJ 27284 이기적인 목봉체조 (Hard)처럼 말이죠. 근데 사실 저는 저 문제도 못 풀었어서;;)

 

+) 그런데 이 글을 쓰고 있는 시점에서 정해는 O(5NM)이라는 걸 들었습니다. 이건 한 번 꼭 풀어보고 싶네요;;

 

E번 : 

뭔가 특정 룰에 따라서 구하면 되는 Ad-hoc 문제가 아니었을 까 생각합니다.

아니면 어느 조건에 따라서 그리디스럽게 구하면 되는 문제였든지요.

아무튼 이 문제를 보긴 했는데도 머릿속에서 해가 잘 떠오르지 못해서 그냥 런쳤습니다.

 

F번 :

일단 Tree 알고리즘을 쓰는 문제인 것 같긴 한데요...

Centroid-Decomposition 막 그런거 쓰는 문제가 아니었을까 생각해보긴 했습니다.

디코방에 올라오는 것 보니 Smaller-to-Larger 및 여러 테크닉들을 활용해서 푸는 문제였다고는 합니다.

 

J번 :

기하 문제인 것을 파악한 순간 문제도 제대로 안 읽고 런쳤습니다.

기하는 너무나 무서워요...

 

후기

요새 맨날 스트릭 유지용 문제들만 풀다보니 문제들을 보고 난이도 파악을 바로하는게 쉽지가 않았습니다. 또한, 오버킬을 해서 푼 문제들도 많아서 이런 부분들은 반성해야겠다는 생각이 들었습니다. 그래도 오랜만에 어려운 대회에 참가하게 되어 재밌었습니다. 그리고 이번 기회를 통해서 HLD를 써본 것도 매우 뜻 깊었던 대회라 생각이 듭니다.

 

다음에 리뷰할 대회는 아마도 제 3회 보라매컵일 것 같습니다. 이번에는 저도 참가자 입장이라서 기대되네요 :)