RUN@KAIST 8/10 방학 연습 풀이

1. 생존자

이 문제를 푸는 데 있어서 아주 중요한 아이디어는, 바로 이것이 스케줄링 문제라는 것을 발견하는 것이다. 다음과 같은 문제를 생각해 보자.

 * N개의 작업이 있다. 각 작업은 S_i 시간 동안 연속적으로 해야 하며, P_i + S_i 시간 내에 완수해야 한다. 작업이 돌아가는 시간을 최대화하여라.

이 문제는 원래 문제랑 완전히 동일한 문제일까? 한번 문제의 조건들을 다시 잘 살펴보자.

 * S_i 시간 만큼 허기를 채울 수 있고 (작업을 돌릴 수 있고), P_i 시간 전에 시작해야 한다는 것은 P_i + S_i 시간 전에 끝내야 한다는 것과 동치이다.

 * 허기를 채울 수 있는 시간동안은 먹지 않는다. 즉 두 개의 작업을 동시에 하지 않는다. 

 * 지금부터 음식을 먹는다 / 허기를 채우지 않으면 바로 굶어죽는다 : 작업이 항상 돌아가고 있어야 한다는 뜻이다. optimal한 스케줄링에서는 이것이 자동으로 만족된다.

 * 생존 시간을 최대화하라 : 허기가 차는 시간의 합이 생존 시간이고, 이는 작업이 돌아가는 시간이다.

이제 데드라인과 작업 시간이 N개 있을 때 작업이 돌아가는 시간을 최대화하는 문제를 해결하자. 

먼저 작업을 실행할 때, 데드라인이 증가하는 순으로 작업을 실행해야 한다. 그렇지 않은 순서가 최적이면, 이를 버블 정렬처럼 바꿔서 항상 증가 순으로 바꿀 수 있기 때문이다. 이제 동적 계획법으로 문제를 해결할 수 있다. DP[i][j] = (1 ~ i개의 작업을 사용해서 시간을 j만큼 소모할 수 있는가?) 로 하면, i번 작업을 하는 가 안 하는가에 따라서 상태 전이가 결정된다. 

루프를 잘 돌리거나 DP[i-1][*], DP[i]만 가지고 다니는 식으로 선형 시간 메모리와 O(N * P_i) 시간 복잡도에 문제를 해결할 수 있다. TC가 100개라 걱정될 수 있지만 잘 작동한다 ~_~ (아니면, std::bitset을 사용해서 TC당 N * P_i / 64에 해결할 수도 있다. 이렇게 하면 500ms 안에 돈다. 이 부분은 left as an exercise..)

2. Feast Coins

각각의 물건을 고르는 횟수가 모두 같아야 하는데, 이 횟수를 T라고 하고 문제를 풀어보자. T가 고정되면, 결국 모든 물건은 T개만큼 가져가야 하기 때문에, 물건을 고를 수 있고 없고는 물건의 개수가 T개 이상인지 미만인지에 따라서 결정된다. 

한편, 굳이 항상 T개를 고른다고 생각하지 말고, 1개를 골라 합을 S / T로 만든다고 생각하자. (T는 S의 약수여야 할 것이다.) 이렇게 생각하면, 모든 S의 약수 T에 대해서, 물건의 개수가 T개 이상인 물건들 중에서 1개씩을 골라서 합을 S / T로 만드는 경우의 수의 합을 세면 된다. 이는 잘 알려진 knapsack 문제로. 모든 약수 T에 대해서 동적 계획법으로 해결하고 더해 주면 TC당 O(sum(S / T) * N) = O(NSlgS) 에 해결할 수 있다.

O(NS) 풀이도 있다. 물건의 개수가 감소하는 순으로 정렬해서, DP[i][j] = (번호 i 이하의 물건들만을 사용해서 합을 j로 만드는 법) 과 같이 knapsack을 한다. 정렬이 되어 있으니, 물건의 개수가 T개 이상이라는 조건을 변호가 몇 이하라는 조건으로 바꿀 수 있다. 고로 저 table이 있으면 합을 S / T로 만드는 법을 간단히 O(1)에 구할 수 있다. 이를 모든 약수에 대해 다 더해주면 된다.

3. Lollipop

먼저 모든 사탕이 길이 2일 때는, 입력의 홀짝성에 따라서 답이 결정된다. 이는 따로 예외처리를 해주자. 고로 길이 1인 사탕이 하나는 존재한다. 이 중 가장 왼쪽에 있는 사탕을 X라고 하자. X의 왼쪽에는 길이 2인 사탕만이 있을 것이고, 오른쪽에는 다양한 사탕들이 있을 것이다. 

오른쪽에 있는 사탕의 길이 합이 S라고 하면, 일단 길이 1부터 S+1까지의 모든 사탕을 만들 수 있다. 항상 다음 두 케이스 안에 속하기 때문이다.

 * Case 1. X에서 시작하는 prefix 중 길이 K인 사탕이 존재함. 

 * Case 2. X에서 시작하는 prefix 중 길이 K인 사탕이 존재하지 않음. 이러한 경우는 X에서 시작하는 길이 K-1의 prefix에 길이 2의 사탕이 붙었음을 의미한다. 고로 길이 K+1의 사탕이 존재하고, 앞에 붙어있는 X를 떼면 길이 K의 사탕을 찾을 수 있다.

길이가 S+1 초과일 때 답은 (X의 왼쪽에 존재하는 길이 2인 사탕 1개 이상) + (X의 prefix) 의 형태일 것이다. 여기서 중요한 것은, X의 가장 긴 홀수 길이 prefix와, X의 가장 긴 짝수 길이 prefix만 뒤에 붙여도 된다는 것이다. 예를 들어 가장 긴 짝수 길이 prefix가 2T의 길이를 가진다고 하자. 어차피 2T <= S+1이고, 2T 길이의 prefix를 찾았다면 2T + 2, 2T + 4, 2T + 6 .... 2T + (왼쪽에 존재하는 길이 2인 사탕 개수) * 2 까지의 수들을 전부 표현할 수 있기 때문이다. 이보다 표현력이 떨어지는 작은 짝수 길이 prefix를 신경 쓸 필요가 없다. 

고로 길이가 S+1 초과일 때는 가장 긴 홀수 / 짝수 길이 prefix를 기억해 두고, 수가 들어올 때마다 해당 prefix 앞에 길이 2인 사탕을 적당히 붙여서 표현하도록 시도해 보면 된다. S+1 이하일 때는 Case 1을 만족하는 지 체크하고, 아니면 Case 2로 넘어가면 된다. 선형 시간에 문제가 해결된다. 

4. Temperature

s일에 시작하는 온도가 최대 몇 일동안 모순이 없을 수 있는지를 판별하는 문제를 풀어보자. i일 온도의 구간을 [A_i, B_i]라 하면, 초기 온도 A_s에서 시작해서, 최대한 온도를 낮게 유지하면서 s+1, s+2 ... 로 날짜를 증가시키고, 만약에 j일에 현재 온도가 B_j보다 큰 상황이 생기면 i일 온도 구간은 j일에서 끝난다. 이를 더 정리하면, i일의 온도 구간이 j일에 끝났다는 것은, A_i > B_j거나 i+1일의 온도 구간이 j일에 끝났다는 것을 뜻한다. 예를 들어, A_i < A_(i+1) 일 경우 무조건 두 번째 케이스일 것이고, 그렇지 않을 경우 첫번째 케이스의 가능성이 있다. 

정답 구간의 끝 점을 늘려나가면서 문제를 해결할 것인데, 끝 점을 늘려나가면 몇개의 온도 구간이 끝나게 될 것이다. i일 이전에 끝난 온도 구간 중 시작점이 가장 큰 것을 Dead(i) 라고 하자. Dead(i) 이전에 시작한 구간들은 모두 i일 전에 끝났고, Dead(i) + 1일에 시작한 구간은 i일에 여전히 살아있으므로 (가정에 의해서), i일을 끝점으로 하는 가장 긴 구간의 길이는 i - Dead(i) 이다. 이제 이 Dead(i) 를 구하면 된다.

일단 Dead(i) >= Dead(i-1) 이다. 또한, i일에 추가적으로 끝날 수 있는 구간 중 시작점이 가장 큰 구간은 j < i && A_j >  B_i를 만족할 것이다. j < i && A_j > B_i를 만족하는 j를 Last(i) 라고 하면, Dead(i) = max(Last(i), Dead(i-1)) 이다. DP스럽게 정의했지만, 실제로는 변수 하나만 가지고 다니면 된다.

이제 Last(i)를 빠르게 구해야 하는데, 먼저 O(nlgn) 풀이를 생각해 보자. A_i 들을 포함하는 스택을 가지고 다니자. 새로운 A_i가 들어왔을 때, 이보다 작거나 같은 값들은 이제 더 이상 의미가 없어진다. 새로 들어온 A_i는 인덱스도 크고 값도 큰 상위호환이기 때문이다. 이들을 스택에서 전부 제거해 주면 스택의 원소들이 단조감소한다. 이분 검색으로 B_i보다 큰 최소 A_i를 찾으면, 이 A_i가 인덱스가 가장 크다. 고로 O(nlgn)에 답을 찾을 수 있다.

아마 이것으로도 충분하지만, O(n) 풀이도 가능하다. B_i보다 큰 A_j를 이분 탐색으로 찾았는데, 이들은 이미 Dead(i)에 반영되었기 때문에 끝점은 앞으로 항상 이들보다는 큰 값이 반영된다. 고로 이들은 스택에 남겨 둘 필요가 없다. 양 끝을 넣고 뺄 수 있는 deque를 사용해서, B_i보다 큰 A_j를 이분 탐색으로 찾지 말고, 데큐의 앞에서 순서대로 빼면서 찾는다. 이렇게 하면 amortized O(n) 시간에 문제를 해결할 수 있다.