2023 경인지역 6개대학 연합 프로그래밍 경시대회 shake! 성균관대학교 선발전 후기

대회 결과

shake!에 처음으로 출전했다. 오프라인 선발전을 통해 10명을 뽑는데, 2등으로 마무리했다.

문제는 2023 아주대 경시대회 Div.1을 빌려서 쳤고, 문제세트는 여기서 확인할 수 있다.

 

A. (AC+3/+9min)

문자열 구현문제인데, 메소드를 몰라서 일일히 loop 돌면서 구현했다. 9분동안 파이썬으로 해버릴까 몇 번은 고민한듯 ㅋㅋ 

---

B. (AC/+52min)

C번보다 훨씬 쉬운데 대회 때는 보고 어려운 것 같아서 넘기고 C 풀고 다시 돌아와서 바로 풀었다. (이러면 안된다..) 순서가 상관없기 때문에 R, U, X의 개수를 모두 구한 뒤, 쓸 수 있는만큼 X를 쓰고 -> 남은 좌표만큼 U, R을 써주면 가능성을 판단할 수 있다. 시간복잡도는 $O(N+K)$이다. 

---

C. (AC+2/+44min)

등차수열과 이분탐색을 활용해 푸는 문제이다. 등차수열 합 공식을 잊어버려서 검색해가면서 풀었다. 쿼리 $Q$개마다 첫 층 블록 수 $a$, 층마다 증가하는 블록의 수 $d$가 주어질 때,

$m$층의 가장 오른쪽 블록 숫자는 $am + \frac {m(m-1)d}{2}$이다. 이를 이용해 $x$가 쓰여있는 층 수를 이분탐색으로 $O(logx)$만에 구하고, 인덱스 또한 $x$에서 빼면 $O(1)$에 구할 수 있다. 전체 시간복잡도는 $O(Qlogx)$이다. 

---

D. (AC+2/+72min)

체스판 뭐시기가 생각난 문제이다. 2차원 격자판의 부분 직사각형에서 같은 이름이 $ \lceil{ \frac {a \times b+1}{2}}\rceil $개가 나와야 한다는건, 과반수를 초과해 나와야 한다는 것에서 착안해,

1. 인접한 두 격자가 같은 이름이어야 한다고 생각했다. 하지만 틀렸다. (맞왜틀?)

2. 그러다 3*3 격자에서 5개를 채울 때 무조건 인접하지 않는다는걸 깨달았고, 3*3 격자에서의 테스트를 추가했다. 그래도 틀렸다. (맞왜틀?)

3. 그러다 1*3 격자에서 2개를 채울 때도 고려해야 한다는걸 깨달았고, 2번을 지우고 1*3 격자에서의 테스트를 추가해 맞았다. (휴~)

---

E. (AC/+87min)

웰노운 2차원 dp 문제이다. $N \times 3000$ dp 테이블을 생성하고, 정답이 $\Sigma_{j=1}^{k} dp(n, j) $ 일 때, 전이함수는 다음과 같다.

$dp(i,j) = \Sigma_{p=max(1, j-k)}^{min(n, j+k)} dp(i-1, p)$이다. 하지만 이대로 구현하면 모든 테이블을 채우는데에 $O(3000\times NK)$가 걸려 시간초과가 뜰 것이다. 그러므로 $dp(i,-)$를 구하기 전 $dp(i-1,-)$ 배열을 누적합으로 채워서 전이함수가 $O(1)$에 작동하도록 최적화한다. 

그렇게 구한다면 시간복잡도는 $O(3000 \times N)$가 되어 통과할 수 있다.

---

F. (AC+6/+177min)

H번을 먼저 풀고 돌아와서 푼 문제이다. 맞왜틀의 연속이었지만 끝끝내 맞았다. 계속 틀린 주 이유는 바깥에서 돌고있는 사람의 도달시간을 구하는 코드가 잘못돼서이다. (그것도 모르고 애꿏은 BFS 코드만 고쳤다 ㅠㅠ)

먼저 이 둘은 $2(N+M-2)$개의 바깥 격자에서만 만날 수 있기에, 연병장 안쪽에 있는 사람에서 시작해 Flood Fill로 $2(N+M)-4$개 지점으로의 최소 도달시간을 채웠다. 이 시간과 바깥에 있는 사람의 $2(N+M)-4$를 비교해 둘이 만날 수 있는 최소 시간을 구한다. 만약 차이가 홀수라면 만날 수 없다.

---

G. (AC/+204min)

못 풀거같아서 보고만 있었는데 KCM Travel이라는 문제와 비슷한 아이디어인 것 같아 블로그를 통해 아이디어를 얻었다.

다익스트라이긴 한데, 최소거리 table을 $N$개 저장하는 것이 아니라 $NK$개를 저장한다. edge의 상태도 (a -> b, w)가 아니라 ((a,j) -> (b,(j+w)%mod), w)처럼 생각할 수 있다. 시간복잡도는 $O(Mlog(NK))$이다.

---

H. (AC/+99min)

수학+조합 문제이다. 먼저 모든 벡터를 최대공약수로 나눠준다. 만약 $(9,-6)$이면 $(3,-2)$ 또는 $(-3,2)$로 값을 줄이는 것이다. 둘 중 어느 값으로 나타내어도 이 문제를 푸는데에는 문제가 없다. 또한, 영벡터 $(0,0)$은 어느 벡터와도 내적값이 0이므로 따로 빼준다. (어차피 최대공약수 계산할 때 divide 0 에러 나서 빼줘야 한다.)

총 벡터가 $N$개, 영벡터가 $M$개일 때 정답에 $\binom{M}{2}+M(N-M)$를 더해준다. 영벡터끼리의 조합, 영벡터와 아닌 벡터의 조합 개수이다. 이제 영벡터가 아닌 것들끼리의 조합만 구하면 된다.

$N-M$개의 벡터마다 좌표가 $(a,b)$라면, $(b,-a), (-b,a)$ 의 개수를 구한다. 이 개수는 map을 활용해 $O(logN)$만에 구했다. 이렇게 구한 합에서 2를 나누고 위의 값을 더하면 정답이 도출된다. 시간복잡도는 $O(NlogN)$이다.

---

J. 못 풀었지만 아이디어

사이클이 딱 하나 있는 그래프에서 트리를 만들었을 때 거리 합을 최소로 만드는 문제이다.

1. 먼저 사이클을 이루는 간선들을 DFS를 활용해 구해준다. 사이클을 이루는 노드 개수가 $X$개라고 하면, 사이클을 이루는 간선을 모두 제거했을 때 컴포넌트 개수는 $X$개(모두 트리 형태)일 것이다.

2. 이 $X$개 트리의 크기를 모두 구하고, 간선을 하나씩 제거하면서 제거했을 때 증가하는 거리를 계산한다. (증가하는 거리를 어떻게 계산할지는 아직 모르겠다.)

3. $X-1$개의 간선을 하나씩 제거해보고, 가장 거리가 가장 적게 증가하는 간선을 제거해 트리 dp로 거리쌍을 구한다.

상당히 복잡해보이는 문제이지만, 시간이 많다면 풀 수도 있었을 것 같다.