RUN@KAIST 7/20 방학 연습 풀이

1. Digit Division

Si = 주어진 숫자의 i자리 prefix를 mod M으로 나눈 나머지라고 하자. Si 배열은 선형 시간에 쉽게 계산할 수 있다.

주어진 숫자들을 적당히 나눈 partition이 대충 [i1 + 1, i2] / [i2 + 1, i3] / [i3 + 1, i4] / ... / [i_{k-1} + 1, i_k] 와 같이 생겼다고 하자. 물론 i1 = 0, i_k = N이다. 이 partition이 올바르려면, 모든 1 이상 k 미만의 idx에 대해서 S_{i_{idx + 1}} = S_{i_ idx} * 10 ^ (i_{idx + 1} - i_idx) (mod M)을 만족해야 한다. 

이 때, S_{i1} = 0 (mod M)임을 알 수 있다. 고로 S_{i2} = 0 (mod M)이다. 그리고 S_{i3} = 0 (mod M)도 만족한다. 계속 하면 S_{i_k} = 0 (mod M) 까지 모든 S_{i_j} 가 0이어야 한다는 결론이 나온다. 아까 저 조건이 partition이 존재할 필요 충분 조건이었으니, 올바른 partition은

 * S_N = 0이며

 * i_2 ... i_{k-1} 과 같은 index들이, S_i = 0을 만족한다

는 조건을 충족함을 알 수 있다. 고로, 처음에 S_N = 0인지 체크하고 (아니면 당연히 0), 아니면 S_i = 0인 1 이상 N-1 이하의 인덱스들의 부분 집합을 아무거나 뽑으면 되니, 2 ^ (그러한 인덱스) 가 답이 된다.

2. Cellular Automaton

각각의 위치에 Ai개의 셀들이 있을 때, 셀들은 원호 상의 거리가 D 이하인 점들끼리 자유롭게 움직일 수 있다. M번의 과정 이후 셀들의 개수를 세는 문제이다.

일반적으로 이러한 문제들은 동적 계획법으로 해결할 수 있다. D[i][j][k] = (i번의 이동 이후, j번째 위치에서 k번째 위치로 갈 수 있는 경우의 수) 라고 하자. i-1번째 이동에서, j번째 위치에서 시작하고 k에서 거리가 D 이하인 위치로 도착하는 모든 경우의 수의 합을 계산해 주면 O(M * N^3) 에 답을 계산해 줄 수 있다. 이 동적 계획법 표가 있다면, M번의 이동 이후, j번째 위치에서 k번째 위치로 갈 수 있는 경우의 수를 계산 할 수 있고, 고로 각 위치의 셀의 개수 역시 세 줄 수 있다.

한편, 동적 계획법을 i번째 이동 후 경우의 수 -> i+1번째 이동 후 경우의 수 와 같이 전개하지 않고, i번째 이동 -> 2*i번째 이동 후 경우의 수와 같이 전개해 줄 수도 있다. 2i번의 이동 이후 j에서 k로 가는 경우의 수는, i번의 이동 이후 셀이 어디 있었는지를 고정시켜주면 구할 수 있기 때문이다. 이제, 빠른 지수승 알고리즘과 비슷한 아이디어로 O(N^3lgM) 시간 안에 M번의 이동 이후의 경우의 수를 계산할 수 있다. 이제 어느 정도 빠른 시간 안에 계산할 수 있게 되었지만, 여전히 시간 복잡도를 더 줄여야 한다.

한편, 셀들이 원형 구조에 있기 때문에, 몇번의 이동 이후 (i + 1) % n번째 위치에서 (j + 1) % n번째 위치로 가는 경우의 수, (i + 2) % n번째 위치에서 (j + 2) % n번째 위치로 가는 경우의 수는 모두 동일하다. 고로, 0번째 위치에서 j번째 위치로 가는 경우의 수들만 알고 있어도, i번째 위치에서 (i + j) % n번째 위치로 가는 경우의 수를 알 수 있다. 그러면, 동적 계획법에서 i번째 이동 후 경우의 수 -> i+1번째 이동 후 경우의 수, i번째 이동 후 경우의 수 -> 2*i번째 이동 후 경우의 수를 계산하는 것이 모두 N^2 시간 복잡도에 가능하다. 고로 O(N^2lgM) 시간에 문제를 해결할 수 있다. 

빠른 푸리에 변환을 사용하면 O(NlgNlgM) 에도 문제를 해결할 수 있다. 

3. Bridge Construction Planning

사실 Blazing New Trails 랑 아주 똑같은 문제인데, 해당 문제에 대한 풀이를 최근 블로그 글로 썼었다. 고로 그 링크로 대체한다. 링크 보기

4. 검역소

N개의 정점이 있는 트리에서 K개의 간선을 적절히 끊어서, 각각의 컴포넌트의 사람의 합의 최댓값을 최소화하는 문제이다. 

답에 대해서 이진 탐색을 하면, K개의 간선을 적절히 끊어서 각각의 컴포넌트의 사람이 합을 X 이하로 만들 수 있는지를 판별하면 된다. 편의상 1번 정점을 루트로 잡고 rooted tree라고 생각하자. 어떤 정점이던간에 X명 초과의 사람들이 그 정점에 살고 있다면 지구가 멸망해도 불가능하다. 고로 그런 경우는 없다고 치자. dfs를 통해서 리프부터 순서대로 보면서 루트로 올려줄 것이다.

만약에 모든 자식 정점들을 다 이어줘도 X명을 초과하지 않는다면 그냥 올려주면 되지만, 그렇지 않을 때는 자식과 연결된 몇개의 간선을 끊어줘야 한다. 최소의 간선을 끊어야 하기 때문에, 자식 정점 중 끊었을 때 가장 많은 사람들이 빠지는 정점들을 그리디하게 끊는 것이 이득이다. 정렬을 한 후, X명을 초과하지 않을 때까지 계속 가장 많은 사람들을 올려준 정점들과의 간선을 끊어준다. X명을 초과하지 않게 조정해 줬으면, 부모로 이어준 후에 나중에 부모에서 끊던지 말던지 처리를 하면 된다. 이렇게 하면 루트까지 모든 정점을 처리할 것이다. 이후 끊어준 간선의 개수를 세서 그것이 K를 넘는지 아닌지로 가능성을 판별할 수 있다.