RUN@KAIST 2018 겨울 1주차 연습 문제

A. 약 팔기

1000000=1000*1000이므로, 1을 1000개, 1000을 1000개 나열하면 된다. 1<=N<=1000000에 대하여 N%1000는 1들로, N/1000은 1000들로 만들 수 있다.

B. 정과프 해적단 (구사과)

문제를 간단히 하여 N개의 섬들이 주어졌을 때 얻을 수 있는 가치가 M 이상인지만을 판별하는 문제를 풀어 봅시다. 주어진 섬들을 x좌표 순으로 정렬한 후 (같을 시 y좌표), 동적 계획법을 사용할 수 있습니다. DP[i] = (i번 섬을 거쳤을 때 얻을 수 있는 최대 가치) 라고 하면, DP[i] = (j < i, Y_j <= Y_i) DP[j] + V[i] 라는 O(N^2) DP 점화식이 나옵니다.

이 O(N^2) DP 점화식을 O(NlgN)으로 최적화 해야 하는데, 먼저 “좌표 압축" 이라는 것을 사용하여 Y_i를 N 이하의 정수로 바꿔 줍시다. DP[i]를 i가 증가하는 순서대로 계산한다면, Y_j <= Y_i인 모든 j에 대해서 DP[j]의 최댓값을 계산해야 합니다. 이는 어떠한 구간의 최댓값을 계산하고, 어떠한 점의 값을 갱신하는 문제입니다. 고로 세그먼트 트리를 사용해서 계산할 수 있습니다. O(NlgN)에 문제를 해결하였습니다.

실제 문제에서는 가치를 M 이상으로 하면서 비용 역시 최소화해야 합니다. 간단하게는, O(N^3lgN) 에 문제를 해결할 수 있습니다. 전체 입력을 강도 순으로 정렬한 후, “최소 강도의 섬" 과 “최대 강도의 섬" 을 고정시킵니다. 강도가 둘 사이에 있는 모든 섬들을 모아서, 위 O(NlgN) 알고리즘으로 M 이상의 가치가 나오는지를 판별해 보면 됩니다.

이를 O(N^2lgN)으로 줄이기 위해서는, 최소 강도의 섬이 고정되었을 때 최대 강도의 섬을 많이 찾지 않아도 된다는 관찰이 필요합니다. 강도 순으로 1번, 2번, … , N번 섬이라 이름을 붙이겠습니다. 1번 섬을 넣고, 가치가 M 이상이 될 때까지 순서대로 섬을 넣습니다. (1, 2, 3, … , 해서 F[1]번까지 넣었다고 합시다.) 1번 섬을 뺀다면, 가치가 M 이상이 안 될수도 있습니다. 그렇다면 F[1] + 1부터 시작해서 계속 섬을 넣어주면 됩니다. 이렇게 되면 2N번 섬을 빼고 넣습니다. 고로 위 O(NlgN) 알고리즘을 O(N)번 실행합니다. 시간 복잡도는 O(N^2lgN)입니다.

C. CodeCoder vs TopForces (구사과)

각각의 사람에 대해서 그 사람이 CodeCoder 몇등인지, TopForces 몇등인지를 이분 탐색으로 셀 수 있습니다. 모든 사람의 레이팅이 다르니 동률은 존재하지 않습니다. (사실 이 “등수" 를 세는 게 좌표압축입니다 ㅋㅋ)

문제에 주어진 것은 방향성 그래프인데, 이 그래프의 Strongly Connected Component를 생각해 봅시다. SCC 상에서 CC P등과 CC Q등이 존재한다면, CC P, P+1, P+2, .., Q 등은 모두 SCC 안에 있습니다. TF에서도 같은 논리를 쓸 수 있습니다. 고로, CC를 기준으로 정렬했을 때, SCC가 같은 사람들은 연속된 구간을 이룹니다.
(CC 1 ~ i등 중 TF 최악의 등수) == i 인 첫 위치를 생각해 봅시다. CC 1등부터 CC i등까지는 같은 SCC에 속합니다. i+1등에 이후에서도 (CC i+1 ~ j등 중 TF 최악의 등수) == j 인 첫 위치를 찾아 봅시다. i+1등부터 j등까지는 같은 SCC에 속합니다. 이렇게 SCC를 묶으면, 각 사람이 들어왔을 때 그 사람이 이길 수 있는 사람의 수를 셀 수 있습니다.

D. Integral Polygon (구사과)

O(N^2) 알고리즘은, 고정된 점을 잡고 해당 점에서 나오는 대각선을 다 해보는 것입니다. 처음에 왼쪽 다각형을 전체, 오른쪽 다각형을 빈 것으로 해놓고, 오른쪽 다각형에 삼각형을 하나 하나 넣어 보면 됩니다. 넓이는 N 혹은 N + 0.5가 나오며, 전체 넓이가 자연수라면 (처음에 아닌지 보고, 아니면 0을 찍고 종료합시다) 오른쪽 다각형이 자연수 넓이를 가지는 것으로 잘 잘렸는지 아닌지를 판별할 수 있습니다. 삼각형의 넓이는 CCW를 통해서 구할 수 있고, CCW는 삼각형의 넓이의 두배가 나오니, 실제로는 홀짝을 보고 판정하면 됩니다.

위 방식대로 개수를 셀 경우, S < T일 경우 그 사이 다각형의 넓이는 CCW(P_S, P_{S+1}, P_{S+2}) + CCW(P_S, P_{S+2}, P_{S+3}) + CCW(P_S, P_{S+3}, P_{S+4}) + … +  CCW(P_S, P_{T-1}, P_{T}) 로 표현할 수 있습니다. 여기서 아이디어는, CCW((X, Y), P2, P3) 은 CCW((X%2, Y%2), P2, P3) 과 같은 홀짝성을 가진다는 것입니다.

X_{i, j, k} = CCW((i, j), P_0, P_1) + CCW((i, j), P_1, P_2) + … + CCW((i, j), P_{k-1}, P_k}) 라고 합시다. 이 표는 O(N)에 구할 수 있습니다.

고정된 S에 대해서, 우리는 S+2 이상인 T 중 X(X_S%2, Y_S%2, T) - X(X_S%2, Y_S%2, S+1) 가 짝수인 경우를 세고 싶습니다. 각 4개의 경우에 대해서, S+2 이상인 T 중, X(i, j, T) 가 홀수인 개수 / 짝수의 개수 등을 배열에 담고, S가 감소하는 순서대로 문제를 풀면 됩니다.

E. King's Heir

연습하신 분들이 쉽다고 하셨습니다...