Educational Codeforces Round 145

A. Garland

code

 

색깔이 있는 전구가 4개 주어진다. 4개의 전구는 모두 꺼져있다. 각 전구의 색깔은 0이상 9이하의 정수로 표현된다.

이제 4개의 전구를 하나씩 스위치(킨 전구를 끄거나 꺼져있는 전구를 키는 것)해서 모두 킬 것이다. 그런데 연속해서 같은 색깔의 전구를 스위치할 수는 없다. 최소 몇 번의 스위치를 해야 모든 전구를 킬 수 있는지 출력하면 된다. 만약 모든 전구를 킬 수 없으면 -1을 출력하면 된다.

 

일단 모든 전구의 색깔이 같으면 모든 전구를 킬 수 없다. 만약 세 전구의 색깔이 똑같고 나머지 하나가 다르다면, 총 6번 스위치를 해야 모든 전구를 킬 수 있다. 그 이외의 경우에는 4번의 스위치만으로도  모든 전구를 킬 수 있다.

 

따라서 모든 전구의 색깔이 같으면 -1, 세 전구의 색깔만 똑같으면 6, 그렇지 않으면 4를 출력한다.

 

B. Points and Plane

code

 

2차원 좌표계가 주어져있다. 정수 좌표인 \( (x, y) \)에 칩을 놓을 수 있는데, 이때 \( |x|+|y| \)만큼의 비용이 필요하다. 또한 칩을 놓을 때, 서로 이웃하는 칸에 칩을 놓을 수 없다.

칩 \(N\)개를 놓는 비용은 각 칩을 놓는 비용의 최댓값으로 정의한다. 칩 \(N\)개를 놓는 데 필요한 최소 비용을 출력해야 한다. \(N\)은 최대 \(10^{18}\)이다.

 

칩 \(N\)개를 놓는 비용을 직접 계산하는 것은 아무리 봐도 너무 어려웠다. 따라서 반대로 특정 비용이 주어질 때 칩을 최대 몇 개 놓을 수 있는지를 계산하고자 했다. 이는 비용이 홀수냐 짝수냐에 따라 달라진다. 비용이 짝수라면 아래의 왼쪽 그림처럼 칩을 둘 것이고, 홀수라면 아래의 오른쪽 그림처럼 칩을 둘 것이다. 회색 칸은 \( (0,0) \), O글자는 칩의 위치를 의미한다.

비용에 따라 둘 수 있는 최대 칩의 개수를 수식으로 정리할 수 있다. 최종 수식은 위의 코드에 있으니 생략한다.

 

비용에 따라 둘 수 있는 최대 칩의 개수를 계산할 수 있으므로, 이분 탐색을 이용하여 칩을 두기 위해 필요한 최소 비용을 계산할 수 있다.

 

C. Sum on Subarrays

code

 

괴상한 문제이다. 배열의 길이 \(n\)이 주어지고 이 배열을 -1000이상 1000이하의 정수로 채워넣어야 한다. 이때, 총 \( \frac{n(n + 1)}{2} \)개의 부분 합을 계산할 수 있는데, 정확히 \(k\)개의 부분 합은 양수이고 나머지 부분 합은 음수가 되도록 배열을 채워넣어야 한다. \(n\)의 크기는 최대 30이다.

 

일단 모든 배열에 \(-1\)을 채우고 생각해보자. 이 경우 부분합은 모두 음수가 된다. 여기서 1번째 숫자를 1000으로 바꾸면 양수인 부분합이 정확히 \(n\)개 추가된다. 이 상태에서 2번째 숫자를 1000으로 바꾸면 양수인 부분합이 정확히 \(n-1\)개 추가된다. 이런 식으로 계속 채워넣으면 부분 합의 개수를 어느정도 조절할 수 있다.

그렇다면 \(k\)가 \(n\)보다 작은 경우에는 어떻게 할까? 이 경우에는 단순히 1번째 값을 \(k\)로 바꾸면 된다. 이렇게 한다면 1번째 원소부터 \(k\)번째 원소까지는 부분 합이 1 이상이고, \(k+1\)번째 원소부터는 부분 합이 0 이하가 된다. 따라서 부분합의 개수가 정확히 \(k\)개 증가한다.

\(k\)가 \(n\)보다 크고 \(2n - 1\)보다 작은 경우에도 비슷하게 할 수 있다. 이 경우에는 1번째 숫자를 1000으로 바꾸자. 그렇다면 \(n\)개의 부분 합은 양수이고, \(k - n\)개의 부분 합을 양수로 만들어야 한다. 따라서 2번째 값을 \(k - n\)으로 바꾸면 된다. 이러면 정확하게 \(k -  n\)개의 부분합이 양수가 된다.

이런 식으로 정확히 \(k\)개의 부분합을 양수가 되도록 할 수 있다. 하지만 이렇게 구현을 해보니 틀렸습니다를 받게 됬다. 문제를 다시 읽어보니 \(k\)개를 제외한 나머지 부분 합은 모두 0이 아닌 음수가 되어야 한다는 것이다. 위처럼 구현하면 일부 부분 합은 0이 될 수 있다. 따라서 맨 처음에 모든 수를 -1 대신 -2로 채워두었다. 또한 부분 합 개수를 조절하기 위해 부분 합 \(k\)개를 추가하기 위해 숫자를 \(k\)로 바꾸었는데, -2를 채워두었으므로, \(2k - 1\)로 바꾸면 정확히 \(k\)개의 부분 합을 추가할 수 있다. 이렇게 구현하니 AC를 얻게 되었다.

 

D. Binary String Sorting

code

 

0과 1로만 이루어진 문자열이 있다. 이 문자열에서 이웃한 두 문자를 바꾸는 비용은 \( 10^{12}\)이고, 한 문자를 제거하는 비용은 \(10^{12} + 1\)이다. 최소한의 비용을 사용해서 문자열을 non-decreasing하게 바꾸어야 한다.

 

한 마디로 문자열을 000...000111...111꼴로 바꾸라는 뜻이다. 이를 일반화하면 특정 \(k\)에 대해 \(k-1\)번째 글자까지는 모두 0, \(k\)번째 글자부터는 모두 1이어야 한다는 것이다. 따라서 \(k-1\)번째 글자 이전에 있는 1을 모두 없애고, \(k\)번째 이후에 있는 0을 없애면 된다.

이제 제거 대샌 이웃한 두 문자를 바꿔서 비용의 이득을 얻을 수 있는 경우를 고려해보자. 생각해보면, \(k-1\)번째 글자가 1이고 \(k\)번째 글자가 0인 경우에만 두 문자를 바꾸어서 비용의 이득을 취할 수 있다. 이 경우 비용의 이득은 \(10^{12} + 1\)이다.

 

각 \(k\)에 대해 필요한 비용을 \(O(1)\)에 구할 수 있다. 주어진 문자열의 누적합을 계산해두면, 특정 문자열 범위 내에 0과 1이 몇 개 있는지 계산할 수 있기 때문이다. 따라서 0이상 \(n\)이하의 모든 \(k\)에 대해서 비용을 계산하고 이 중 최솟값을 출력하면 된다.

 

E. Two Tanks

code

 

두 개의 탱크가 주어진다. 두 탱크의 용량은 각각 \(a\)와 \(b\)로 정해져있다. 이제 총 \(n\)번 두 탱크에 있는 물을 \(v_i\)만큼 옮긴다. \(v_i\)가 양수면 첫 번째 탱크에서 두 번째 탱크로 최대 \(v_i\)만큼 옮기고, 음수면 두 번째 탱크에서 첫 번째 탱크로 최대 \(-v_i\)만큼 옮긴다. 만약, 옮길 물이 부족하거나 옮길 탱크의 용량이 부족하다면 그만큼 옮기는 물의 양을 줄여서 조절한다.

처음 두 탱크에 있는 물의 양을 \(c, d\)라 하자. 그렇다면 각 \(c, d\)에 대해 \(n\)번 물을 옮겼을 때, 첫 번째 탱크에 얼마만큼의 물이 남아있는 지 계산해야 한다.

 

\(n\)이 최대 10,000이고, \(a, b\)는 각각 최대 1,000이므로 naive하게 \(O(nab)\)로는 풀 수 없다. 따라서 최적화하는 방향을 생각해야 한다.

 

최적화를 위해서 식을 먼저 정리해보자. 일단 현재 물의 양이 각각 \(c, d\)일 때, \(v_i\)만큼 물을 옮긴 후 첫 번째 탱크에 있는 물의 양 (c\)를 계산해보자. 편의상 \(t = c + d)\라 하자.

일단 물을 옮겼을 때, \(c, d\)가 음수가 되어서는 안될 것이다. 또한 \(c, d\)가 각각 \(a, b\)보다 커져서는 안된다. 이를 이용해 가능한 \(c\)의 범위를 구할 수 있다. 먼저 \(c\)의 최솟값을 계산해보자. 일단 \(c\)는 0보다 작아질 순 없고, 또한 모든 물을 두 번째 탱크에 부었을 때, 남는 물은 첫 번째 탱크에 담아두어야 한다. 따라서 \(c\)의 최솟값은 \(\max (0, t - d) \)가 된다.

 

똑같은 방식으로 \(c\)의 최댓값을 계산해보자. 일단 \(a\)보다 커져서는 안된다. 탱크 용량보다 더 많은 물을 담을 수 없기 때문이다. 또한, 총 물의 양인 \(t\)보다 커질 수도 없다. 물의 총 합인 \(t\)는 변하지 않기 때문이다. 따라서 \(c\)의 최댓값은 \( \min(a, t) \)가 된다.

 

이렇게 \(c\)의 범위를 제한할 수 있다. \(c\)의 가능한 최솟값을 \(m = \max (0, t - d)\), 최댓값을 \( M \min(a, t) \)라 하자. 그렇다면 \(v_i\)만큼 물을 옮긴 후 \(c\)의 물의 양은 \( \text{clip}(c - v_i, m, M)\)이 된다 (clip의 정의). 이렇게 식을 써두면 최적화할 방법이 보인다!

 

일단 \(t\)를 고정해두자. 그렇다면 \(m\)과 \(M\)의 값도 고정, 즉 상수로 취급할 수 있다. 이제 \(c\)의 초기 값을 \(m\)부터 \(M\)까지 세팅하고 이 값들을 배열로 저장해보자. 그렇다면 맨 처음 값은 \( C = [m, m+1, m+2, \dots, M-2, M-1, M]\)이 될 것이다. 편의상 \(m = 0, M = 7\)이라 해보자. 그렇다면 맨 처음 값은 \( C = [0, 1, 2, 3, 4, 5, 6 ,7]\)이 된다. 이제 물을 먼저 \(v_1\)만큼 옮기면 그 결과는 \(C = \text{clip}(C - v_i, m, M)\)이 될 것이다. \(v_1 = 2\)라 해보자. 그렇다면 첫 번째로 물을 옮긴 결과는  \( C = [0, 0, 0, 1, 2, 3, 4, 5]\) 가 된다. 이 상태에서 \(v_2 = -4\)라 해보자. 그렇다면 두 번째로 물을 옮긴 결과는  \( C = [4, 4, 4, 5, 6, 7, 7, 7]\)이 된다. 이런 식으로 계속 물을 옮기는 과정을 반복해보면 관찰을 할 수 있다. 배열 \(C\)의 형태가 \([x, x, \dots, x, x+1, x+2, \dots, y-2, y-1, y, y, \dots, y, y] \)가 된다는 것이다. 즉, 일정하다가 중간부터 1씩 늘어나고 다시 어느 시점부터 일정한 값을 가지게 된다.

 

만약 배열 \(C\)를 위처럼 직접적으로 구하면 총 \(n\)번의 연산이 필요하고 고정해야 할 \(t\)값은 \(a + b\)개이며, 배열 \(C\)의 크기는 최대 \(a\)이므로 시간복잡도가 \(O(na(a+b) \)로 여전히 너무 오래 걸린다. 하지만 배열 \(C\)가 위와 같은 특징을 가진다는 것을 확인했으므로 보다 빠르게 구할 수 있다. 나는 아래와 같은 방법으로 구했다.

 

먼저 \(C = [x, x, \dots, x, x+1, x+2, \dots, y-2, y-1, y, y, \dots, y, y] \)라 할 때, \(x\)값을 구한다. 이는 가능한 가장 작은 \(c\)값에 대해 \(n\)번의 연산을 하면 되므로 \(O(n)\)에 구할 수 있다. 이제 값이 \(x\)가 아닌 원소 중 가장 앞에 있는 원소를 구한다. 이는 이분탐색을 통해 구할 수 있으며, \(O(n \log a )\)에 구할 수 있다. 배열의 길이가 최대 \(a\)이기 때문에 \( \log a\)번의 계산을 해야 하고, 특정 원소의 값을 구하려면 \(n\)번의 연산을 해야 하기 때문이다.

이제 배열 \(C\)를 \(C = [x, x, \dots, x, x+1, x+2, \dots] \)와 같이 먼저 계산해둔다. 즉, 특정 위치까지는 \(x\)로 채우고, 그 이후에는 1을 더해가면서 배열을 채운다. 마지막으로 \(y\)값을 구한다. 이는 가능한 가장 큰 \(c\)값에 대해 \(n\)번의 연산을 해서 구할 수 있다. 이후 배열 \(C\)에서 \(y\)보다 큰 값을 모두 \(y\)로 대체하면 우리가 구하고자 하는 배열 \(C\)를 \(O(n \log a )\)안에 구할 수 있다. 배열 \(C\) 총 \(a + b\)개의 \(t\)에 대해서 구해야 하므로, 가능한 모든 \(c, d\)에 대해 문제의 정답을 구하는 데 필요한 시간 복잡도는 \( O(n \log a (a+b)) \)이다. 이를 코드로 구현하여 제출하니 약 0.5s 정도 걸렸다. 시간 제한이 2초인 걸로 보아 상수가 많이 붙도록 구현하면 시간초과가 날 위험도 있을 것 같다.

 

후기

B번 문제를 풀 때 수식정리하다가 말려서 20분만에 1번 틀리고 겨우 풀렸다... friend stanings를 보니까 제일 늦게 풀었었다. 항상 수학이나 수식을 정리하는 부분이 나오면 뭔가 조금 늦어지는 거 같다. 그래도 그 뒤의 \(C, D\)는 거의 constructive, case work 냄새가 진한 문제들이었고, 운좋게도 빠르게 특징을 관찰해서 빨리 밀 수 있었다. \(E\) 문제는 뭔가 어렵긴 했지만 오래 관찰해서 43분만에 맞출 수 있었다. 모든 문제를 풀고 나니 \(F\)번을 30분 안에 풀어야 했는데, \(E\)번 문제를 푸는 데 걸리는 시간을 고려하면 풀 수 없을 것 같아 포기하고 나왔다. 그런데 풀린 문제 수를 보니 \(E, F\)가 풀린 수가 거의 똑같아, 문제 배치 순서를 고려하면 \(F\)가 \(E\)보다 좀 쉬운 것 같았다. 30분안엔 풀지 못했겠지만 한 40분 정도 남았다면 풀 수 있었을 것 같다.