송도고 코드마스터 2023 Open Contest

다들 시험기간일텐데 빈집털이를 해서 1등을 먹었다.

 

A. 코드마스터 2023

-> 단순구현

 

B. 점심시간 레이스

-> 모든 사람은 오른쪽으로 가서 내려가는 경로를 취한다.

-> 따라서 F + (M - D) 중에서 최솟값을 구하면 된다.

 

C. 정보 선생님의 야망

-> 모든 가짓수를 시도하면 된다.

-> 상수들이 넉넉해서 비트가 2개인 모든 숫자에 대해 확인해보면 됨

 

D. 배고파

-> 어차피 X, Y는 60 이하일 것이기 때문에 많아야 60^2가지 만이 2^X + 2^Y로 표현 가능하다

-> 따라서 미리 모두 만들어두고 제일 가까운 것을 고르면 된다.

-> 그리디한 사고도 가능하지만, 숫자가 넉넉해서 그럴 필요가 없다.

 

E. 수학 선생님의 고민

-> 근의공식을 쓰면 두 근을 만들 수 있다. -> 우선 판별식이 제곱수가 아니라면 가볍게 버리자

-> 그러면 두 근 x1, x2는 p1/q1, p2/q2로 나타낼 수 있다.

-> 정수로 인수분해해야하므로 (q1*x - p1) * (q2*x - p2)가 되어야 한다.

-> 따라서 만일 x^2의 계수인 N이 만일 q1 * q2로 나누어지지 않으면 불가능하다.

-> 나누어지면 (N = q1*q2*d)인거고 (q1 * d, -p1*d), (q2, -p2)를 답으로 제출해주면 된다.

 

F. S리그

-> 열심히 생각하면 된다.

-> 대충 사고과정은 U자형으로 처음에 왼쪽 위에서 시작해서 마지막에 오른쪽 위로 가는 방식이다.

-> 위의 방식은 1번과 N번을 연결시키기 위해서 고안한 방식이다.

    -> N번 사람을 대충 (x, 1e9)에 박아버리면 대충 웬만한 점(1번 사람)과 연결이 가능하기 때문이다.

 

G. 교실 불 끄기

-> 올라갔다 내려오는 것은 한 사람에 의해서 이루어지는 작업이다

-> 하지만 그냥 올라가는 사람 2명을 만들고 그 두 사람이 맨 위에서 만나는 것이 생각하기 편하다.

-> DP[i] = (i & 1이면 첫 번째 사람은 오른쪽에 있단 뜻, i & 2면 두 번째 사람은 오른쪽에 있다는 뜻)

-> 따라서 매 층의 불을 모두 끌 때 적당히 nxt_dp[i] = dp[j] + (머시기)가 되도록 dp를 만들면 된다.

 

필자는 어차피 1과 2는 상태가 동일하기 때문에 state가 3개인 dp를 했다.

그 후 3 * 3가지 경우에 대해서 모든 상태전이를 만들어주었다.

 

H. 조별수업

 

수학적인 dp를 졸라 하다가 알고보니 상당히 간단한 풀이가 있음을 깨달았다.

dp[i][j][k] : I가 최소인 그룹을 만들것이고, 현재 남은 사람은 J명이며 K개의 그룹을 만들었다.

-> 이때 K < 50이기 때문에 MAXI * MAXJ * MAXK < 1e8

 

그렇다면 dp[i][j][k] = sum{ dp[x(< i)][j - i][k] * C(j - i, i - 1) * factorial[i] }으로 나타낼 수 있다.

-> 이때 C(j - i, i - 1) * factorial[i]는 모두 동일하다

-> 따라서 prefix sum 감성으로 sum{dp[x(<i)][j - i][k]}를 관리해주면 된다.

 

에디토리얼의 풀이가 더 간단한 듯하니 참고.

 

I. 사람이 먼저되라

 

대회 중에 작성한 I 풀이가 아마도 맞을 것으로 예상된다. 

슬프게도 작은 오류가 있어서 AC를 받아내지는 못했고, 지금도 딱히 증명은 하지 못했다

(1e5 짜리 데이터로 랜덤을 돌리면 TLE가 나오지 않고, 1e3으로 브루트포스랑 비교하면 답이 같다)

엄밀하지 않은 풀이이고 틀릴 수도 있는 풀이.

 

*문제가 백준에 올라와서 제출해보니 시간이 매우 넉넉하게 통과를 했다.

 

일단 딱히 다른 생각이 나지 않기에 제일 단순한 방식을 채택했었다.

-> Max가 되는 간선을 기준으로 답을 모두 더하자.

-> 즉 가중치를 기준으로 정렬해서 하나하나 이어나가자.

-> 그러면 현재 u - v, 가중치 w를 연결한다고 가정하자.

-> 그러면 (u와 연결된 점들) ~ (v와 연결된 점들)의 경로는 무조건  max값이 w가 된다.

-> x와 연결된 간선들의 개수가 cnt[x], 이들의 x에서부터까지의 거리의 합을 sum[x]라고 하자.

-> 그러면 이때 w, cnt[u], sum[u], cnt[v], sum[v]를 이용하여 답을 구해나갈 수 있다.

 

위의 과정을 어떻게 빠르게 할 수 있을까?

일단 cnt[x]는 union-find를 통해서 빠르게 구할 수 있다.

Union-find를 했을 때 leader는 올바른 sum값을 가지고 있다고 가정하자.

-> 그럼 leader에서부터 x까지 내려오면서 x에서의 sum값을 구할 수 있다.

예를 들어 leader - y가 가중치 w인 간선으로 연결되었다고 가정하자

그러면 sum[y] = sum[leader] + (cnt[leader] - cnt[y]) * w - (cnt[y]) * w가 된다.

-> 이제 트리에서 관리한다는 것을 알았으니 sum, cnt의 정의를 바꾸자.

-> root가 Leader일때 sum[x] = (x에서 subtree 점들까지의 거리), cnt[x] = (x의 subtree의 크기)

-> 우리는 흔한 dfs 문제들에서 sum[x]와 cnt[x]를 관리하는 법이 익숙하다.

 

그러면 다음과 같은 생각을 할 수 있다.

모든 점에 대해서 Leader -> x의 거리가 적당히 짧게 되는 leader를 잡는 것이 좋겠다.

-> 트리에서 이런 작업을 하면 centroid가 생각날 수밖에 없다.

따라서 적당히 트리들을 관리하는데, 항상 centroid가 root가 되도록 트리를 관리하자.

 

그러면 특정 정점을 root로 만들어주는 것만 구현해주면 된다.

-> 이것은 spin이라는 함수를 만들어주면 된다.

-> p[x] = y였던 상태에서 p[y] = x로 바뀐다면 sum[x], sum[y], cnt[x], cnt[y], p[x], p[y]만 바뀌므로 빠르게 바꿀 수 있다.

x를 root로 만들어주기 위해서는 x -> Leader까지 spin을 통해서 올라가면 된다.

 

그렇다면 다시 본론으로 돌아와서 u - v를 이어준다면 (이때 기존의 leader는 leaderU, leaderV라 하자)

1) v를 자신이 포함된 트리에서 root로 만들어준다.

2) p[v] = u가 되도록 v가 속한 트리를 u 밑에 붙여준다.

3) 새로운 leader는 반드시 leaderV - leaderU 상의 경로에 있을 것이니 잘 선택해서 root로 만들어준다.

 

이 풀이는 현재 Centroid로 정하면 어떻게든 빠르게 코드가 돌지 않을까? 를 가정으로 굴리고 있다.

시간제한이 5초이고 로컬에서 테스트를 해보면 1e6 정도까지는 버텨낸다.

다만 트리가 특이한 형태라면 안될 수도 있다.