2022 ICPC Seoul Regional 예선 후기

---

안녕하세요 Gliver 입니다.

이번 글은 2022.10.08 에 있었던 2022 ICPC Seoul Regional 예선에 대한 글입니다.

 

 

프리징된 스코어보드

이번 대회는 같은 학과 사람들과 함께 나가게 되었다. (편의상 α, β로 칭하겠다)

이번 대회에서 내가 푼 문제는 C, E, F이고,  α가 A, K를 풀었다.

 

이번 대회에서 주로 α와 내가 키보드를 잡고 진행하게 되었다.

그리고 β는 문제에 대한 설명과 조언을 해주었는데 도움이 많이 됐던 것 같다.

 

 

 

E. Gift Discount (00:17)

개발환경 세팅을 마치자마자 β가 나에게 설명해 준 문제이다.

보자마자 떠오른 아이디어는 '가장 싼 물건들을 사야겠네'와 '산 물건들 중에서 가장 비싼 물건 $a$개를 할인하면 되겠네' 였다.

이를 prefix sum을 이용하여 모든 경우를 살펴보았으며 $O(n)$으로 풀 수 있었다.

 

 

 

A. Balance Scale (00:23)

내가 E를 푼 후에 α가 바로 코드를 짜서 풀어낸 문제이다. 문제는 안 봐서 모르겠지만 쉬운 문제라고 했다.

 

 

 

C. Container Rearrangement (00:36)

E를 푼 후에 β가 C번을 설명해주었다.

들어보니, 모든 높이의 차가 1이하가 되게 하는 최소 연산(?)횟수를 구하는 문제였다.

만들어야 하는 결과 상태는 정해져 있었고, 이를 만드는 작업은 그리디하게 수행하면 항상 최소 횟수가 되었다.

 

원래 배열을 정렬된 상태를 $arr$, 만들어야 하는 배열의 정렬된 상태를 $brr$이라고 하자.

이제 인덱스를 0부터 n-1까지 살펴 보면된다.

만약 $arr[i] \leq brr[i]$ 이면, ans += abs(arr[i] - brr[i]) 를 수행한다.

만약 $arr[i] > brr[i]$ 이면, break를 수행한다.

참고로, 수의 범위가 크므로 변수 ans는 long long 으로 선언해줘야 한다.

 

정렬을 해야 하므로 시간 복잡도는 $O(n \ logn)$ 이다.

 

 

 

F. Islands Tour (01:17) [+1]

C를 풀자, α가 F번을 설명해주었다. 

F번은 방향 그래프가 주어지고 이때 가장 긴 경로의 길이를 구하는 문제이다.

그래프에는 1개 이상의 컴포넌트가 있으며, 각 컴포넌트는 후속 노드 그래프를 만족한다.

따라서, 각 컴포넌트마다 가장 긴 경로를 찾고 그 중에서 가장 긴 길이를 출력하면 된다.  

 

이제 우리가 해야할 일은 후속 노드 그래프에서 가장 긴 경로를 찾는 것이다.

후속 노드 그래프는 하나의 사이클과 그 사이클로 가는 경로로 구성되어 있다.

따라서, '사이클로 가는 가장 긴 경로 + 사이클의 크기' 를 구해주면 된다.

 

사이클로 가는 가장 긴 경로는 in_degree(진입차수)가 0인 노드를 먼저 탐색하면 쉽게 구할 수 있으며,

사이클의 크기는 사이클에 포함된 노드에서 dfs를 돌리면 쉽게 구할 수 있다.

따라서, 시간 복잡도는 $O(m+n)$을 만족한다.

 

 

 

K. Temporal Graph (02:37) [+1]

내가 F를 푸는 동안 α와 β가 G번 문제를 읽고 나에게 설명해 주었다.

그런 후에 G는 내가 맡게 되었고, α와 β는 K를 풀러 갔다.

문제를 안 읽어봐서 잘 모르겠으나, 2차원 DP로 풀린다고 하였다.

 

 

 

G. Jar Game

F를 푼 후에 대회가 끝나기 전까지 약 2시간을 푼 문제이다.

문제 설명을 듣고 나서, 항아리가 3개 있으며 돌을 가져가는 게임 문제였다.

비슷한 문제를 1달 전쯤에 백준에서 보았는데.. 진짜 풀지는 않고 보기만 했다.. 🥲

 

현재 상태에서 할 수 있는 선택은 3가지로 나눌 수 있으며, 이 중에서 어떤 선택이 best인지는 현재 알 수 없다.

따라서, 그리디하게 풀 수 없으며 DP 문제라는 것을 직감적으로 느꼈다.

 

DP table은 $dp[k][a][b][c]$일 것 같은 확신이 들었다. 하지만, 생각이 꼬여서 2시간 동안 삽질을 한 것 같다.

 

집에 돌아와서 다시 풀어보았더니 다음과 같이 DP table을 정의하면 쉽게 풀 수 있었다.

$dp[k][a][b][c]$: 항아리에 각각 a, b, c개의 돌이 들어 있고, k개를 가져갈 수 있을 때 얻을 수 있는 최대 점수

$$dp[k][a][b][c] \small{= a+b+c - min(dp[k+1][max(a-k, 0)][b][c],}$$

$$\small{dp[k+1][a][max(b-k, 0)][c], \ dp[k+1][a][b][max(c-k, 0)])}$$

 

아무리 많은 라운드가 진행되어도 약 30번 라운드 안에는 끝나므로 $k \leq 30$ 이고 $a, b, c \leq 100$ 이다.

따라서, 약 3000만 번의 연산이면 DP table을 완성할 수 있다.

 

 

 

느낀점

아쉽게도 학교 1등은 하지 못했으며, G번까지 풀었으면 전체 등수로 본선을 갈 수 있었을 것 같은데 풀지 못한 게 아쉽다.

그래도 혹시 모르니.. 본선 진출팀이 나올 때까지 기도(?)나 하며 살아야겠다.