Educational Codeforces Round 135

 A. Colored Balls: Revisited

code

문제 설명

\(N\)종류의 공이 각각 \(cnt_i\)개씩 있다. 총 공의 개수는 홀수 개이다.

여기서 서로 다른 색깔은 가진 두 공을 계속 없애나갈 것이다. 그렇다면 마지막에는 같은 색깔을 가진 공만 남을 것이다.

이때, 남은 공의 색깔로 가능한 색깔 중 하나를 출력하면 된다.

알고리즘

만약 한 색깔의 공이 \(\frac{N + 1}{2}\) 개 이상 있다면, 맨 마지막에는 무조건 그 색깔의 공이 남게 된다. 다른 색깔인 공의 개수를 모두 합쳐도, 그 색깔인 공의 개수보다 더 작기 때문이다. 따라서 \(\frac{N + 1}{2}\)개 이상인 색깔의 공이 존재한다면, 그 색깔을 출력하면 된다.

그 이외의 경우에는 어느 공이든 남게 할 수 있다. 따라서 이 경우에는 아무 공이나 출력하면 된다.

 

B. Best Permutation

code

문제 설명

길이 \(N\)의 순열이 주어진다. 이 순열을 이용하여 값 \(x\)를 계산한다.

1번째 원소부터 \(N\) 번째 원소까지 보면서 만약 해당 원소가 \(x\) 보다 크면 \(x\)에 해당 원소의 값을 더하고, 그렇지 않다면 \(x\)를 0으로 바꾼다.

마지막 원소까지 사용하여 \(x\)를 계산한 결과가 최대가 되도록 하는 순열을 아무거나 출력하면 된다.

알고리즘

먼저, 가능한 최댓값이 무엇인지를 알아내야 한다.

먼저 맨 마지막 원소를 이용해 \(x\)를 계산할 때, \(x\)는 마지막 원소보다 작아야 한다. 그렇지 않으면 최종 결과가 0이 되기 때문이다. 따라서 가장 이상적인 상황은 마지막 원소가 가장 큰 값인 \(N\)이고, \(x\)가 \(N-1\) 인 경우이다. 따라서 최댓값은  \(2N-1\) 이라 추측할 수 있다. 이제 실제로 \(2N-1\) 을 만들 수 있는지 확인해봐야 한다.

 

마지막 계산 직전에 \(x\)가 \(N-1\) 이 되도록 하는 쉬운 방법은 마지막에서 두 번째 원소가 \(N-1\)이 되도록 하고, 이전에 \(x\)가 0이 되도록 하는 방법이다. 배열의 길이가 짝수인 경우를 생각해보자. 그렇다면 먼저 \(a_i = i\)가 되도록 배열을 만들고, \(2i-1\) 번째 원소와 \(2i\) 번째 원소를 바꿔준다. 물론 맨 마지막의 \(N-1\), \(N\) 번째 원소는 바꾸지 않는다. 그렇다면 배열은 \([2, 1, 4, 3, 6, 5, \dots, N - 1, N]\)과 같이 될 것이다. 이제 이 배열에서 \(x\)를 계산하는 과정을 보면, \([0, 2, 0, 4, 0, 6, 0, \dots]\)와 같이 짝수번째에 있는 홀수를 만날 때마다 \(x\)가 0이 된다. 따라서 \(N-1\) 번째 원소를 계산하기 직전에도 \(x\)는 0이 될 것이고, 따라서 최종 결과 \(x\)는 최대가 된다.

배열의 길이가 홀수일 때에도 \([1, 3, 2, 5, 4, 7, 6, \dots]\)와 같이 배열하면 된다.

C. Digital Logarithm

code

문제 설명

길이가 \(N\)인 두 배열 \(a\)와 \(b\)가 주어진다. 두 배열 중 한 배열에서 한 원소 \(x\)를 골라 이 값을 \(f(x)\)로 바꾸는 연산을 할 수 있다. \( f(x) \)는 \(x\)를 10진수로 나타낼 때 숫자의 개수이다. 순서를 고려하지 않고 배열 \(a\)와 \(b\)의 값이 모두 똑같아지도록 할 때, 최소 몇 번의 연산을 해야 하는지 출력해야 한다.

알고리즘

먼저 배열 \(a\)와 \(b\)의 가장 큰 두 값을 고려해보자. 만약 두 값이 같다면 두 값은 배열에서 제거를 해도 무방하다. 하지만 한쪽이 더 크다면 그 값에 무조건 연산을 해 주어야 한다. 왜냐하면 \( f(x) \)의 결과는 항상 \(x\) 보다 같거나 작기 때문에 다른 값을 제일 큰 값으로 바꿀 수 없기 때문이다. 따라서 큰 쪽에 연산을 취해주면 된다. 이를 모든 원소가 제거될 때까지 반복하여 연산하면 최소한의 횟수로 배열 \(a\)와 \(b\)가 똑같아지도록 할 수 있다.

우선순위 큐를 이용해 쉽게 구현할 수 있다.

D. Letter Picking

code

문제 설명

길이가 짝수이고 알파벳 소문자로 이루어진 문자열 \(s\)가 주어지고, Alice와 Bob은 이 배열을 이용하여 대결을 한다.

맨 처음 Alice와 Bob은 서로 빈 문자열을 가지고 있다. Alice 먼저 턴을 시작하고, 두 플레이어가 턴을 번갈아 한다.

각 턴에는 문자열 \(s\)의 양 끝 문자 중 하나를 선택하고 이를 자신의 문자열 맨 앞이 붙여야 한다.

문자열 \(s\)가 사라질 때까지 게임을 반복한다. 두 플레이어의 문자열을 비교하여 사전 순으로 앞서는 쪽이 이긴다.

두 선수 모두 게임을 최적으로 플레이할 때, 누가 이기는지, 또는 비기는지를 출력해야 한다.

알고리즘

먼저 문자열 \(s\)에서 양 끝에 있는 문자만 선택할 수 있으므로, \(dp [l][r]\)을 \(s[l:r]\)이 주어질 때 이기는 사람으로 정의한다. 다. 내 구현에서는 Alice가 이기면 \(dp[l][r] = 3\), Bob이 이기면 \(dp[l][r]=1\), 비기면 \(dp[l][r]=2\)로 정의하였다.

먼저 빈 문자열, 즉 \(l > r\)이면 \(dp[l][r] = 0\) 이다. 이제 점화식을 구해야 한다.

 

양 쪽 모두 왼쪽 문자를 선택하는 경우를 고려해보자. 그러면 Alice는 \(s [l]\), Bob은 \(s[l-1]\)을 선택하게 된다. 만약 \(s[l]\), \(s [l+1]\)이 서로 다른 문자라면, 두 문자는 플레이어의 맨 앞에 위치하는 문자이므로, 이 문자에 의해 결과가 난다. 만약 두 문자가 같은 문자라면 이 게임의 결과는 \(dp [l+2][r]\)과 같게 된다. 이렇게 두 플레이어 모두 왼쪽을 선택한 결과인 \(res_{LL}\)을 구할 수 있다. 마찬가지로, Alice가 왼쪽, Bob이 오른쪽을 선택한 결과인 \(res_{LR}\)을 비롯해 \(res_{RL}\), \(res_{RR}\)도 비슷한 과정으로 구할 수 있다. Alice는 결과가 커지는 방향으로 행동하고, Bob은 결과가 작아지는 방향으로 행동하므로, Alice가 먼저 행동한다는 것을 고려하면, \(dp [l][r] = \max(\min(res_{LL}, res_{LR}), \min(res_{RL}, res_{RR}))\)의 점화식을 구할 수 있다. \(dp [1][len(s)]\)를 계산하여 누가 이기는지를 계산할 수 있다.

E. Red-Black Pepper

code

문제 설명

총 \(N\)개의 음식이 존재한다. 이 음식에는 빨간 후추, 검은 후추 중 하나만 뿌릴 것이고, 모든 음식에는 후추를 뿌려야 한다. \(i\)번 음식에 빨간 후추를 뿌리면 맛은 \(a_i\)가 되고, 검은 후추를 뿌리면 맛은 \(b_i\)가 된다. \(N\)개의 음식에 대해 맛의 합이 최대가 되도록 후추를 \(N\)번 뿌릴 것이다.

지금 후추가 없기 때문에 가게에서 후추를 사야 한다. 총 \(M\)개의 가게가 존재하고, \(i\)번째 가게는 빨간 후추를 \(x_i\)개 묶음으로, 검은 후추를 \(y_i\)개 묶음으로 판다. 각 음식마다 후추를 1개 뿌려야 하고, 마지막에 후추가 남으면 안된다. 즉, 각 묶음을 \(x\), \(y\)개 샀을 때, \( x x_i + y y_i = N\)이 되어야 한다.

\(i\)번째 가게에서 후추를 살 때, 가능한 맛의 최댓값을 구해야 한다. 만약 \(i\)번째 가게에서 정확히 \(N\)개의 후추를 사는 것이 불가능하다면 -1을 출력해야 한다.

알고리즘

음식의 순서를 \(b_i - a_i\) 순서로 정렬하자. 그러면 각 후추를 \(X, Y\)개 쓴다고 할 때, 앞의 \(X\)개의 음식에 빨간 후추를 쓰고, 뒤의 \(Y\)개의 음식에 검은 후추를 쓰는 것이 최적이다. 따라서 구매할 후추의 개수를 정하면, 음식의 맛을 누적합을 이용해 \(O(1)\)로 구할 수 있다. 하지만 가게의 종류에 따라 살 수 있는 후추의 개수가 달라진다.

 

먼저 \(x x_i + y y_i = N\)의 정해는 확장된 유클리드 호제법을 이용하여 구할 수 있다. 만약 \(gcd(x_i, y_i\))가 \(N\)의 약수가 아니라면, \(N\)개의 후추를 살 수 없으므로 -1을 출력하면 된다.

 

\(gcd(x_i, y_i) \)가 \(N\)의 약수라면 이제 \(x x_i + y y_i = N\)을 만족하는 해를 하나 구할 수 있다. 또한 \(x, y\)에 각각 \(\frac{y_i}{gcd(x_i, y_i)} = x_{add}\), \( \frac{x_i}{gcd(x_i, y_i)} = y_{add}\)을 더하고, 빼주어도 그 결과는 \(x x_i + y y_i = N\)을 만족한다. 이분 탐색을 이용하여, \(x x_i + y y_i = N\)를 만족하고 \(x\)가 0 이상인 결과 중, \(x\)가 최소인 결과를 구할 수 있다.

 

위 과정으로 \(x\)가 음이 아니면서 최소인 \(x, y\)를 구한다. 만약 \(y\)가 음수라면, \(x, y\)가 모두 음수가 아닌 \(x x_i + y y_i = N\)의 해가 존재하지 않으므로 -1을 출력해야 한다. 따라서 \(x, y\)가 모두 0 이상인 경우를 고려해보자. \(x\)에 \(x_{add}\)만큼 더하고, \(y\)에 \(y_{add}\)만큼 빼면서 맛을 계산하고, 그 중 최댓값을 출력해도 된다. 하지만, \(x_{add}\), \(y_{add}\)가 매우 작다면, 더하고 빼는 과정을 많이 반복해서 시간초과가 나게 된다. 하지만 음식을 선택할 때, \(b_i - a_i\)를 기준으로 선택하므로, 초기 \(x, y\)에서 \(x_{add}\), \(y_{add}\)를 \(k\)번 더해고 뺐을 때 음식의 맛을 \(f(x)\)라 하면, \(f(x)\)는 볼록 함수이다. 따라서 삼분 탐색 등을 활용하여 \(\log\) 스케일 시간안에 음식의 최대 맛을 계산할 수 있다.