Codeforces Global Round 19

A. Sorting Parts

 

Problem - A - Codeforces

 

길이 n인 array A를 consecutive한 두 partition [1 : i], [i + 1 : n]으로 나누어서 각각 정렬하였을 때, A는 정렬되지 않을 수 있는지를 물어보는 문제.

 

 

i를 기점으로 왼쪽 부분에서는 max 값을, 오른쪽 부분에서는 min 값을 구하여 max 값이 min 값보다 크다면 가능함을, 그렇지 않으면 다른 i를 살펴보고 그런 i가 없다면 불가능함을 출력하였다.

 

 

B. MEX and Array

 

Problem - B - Codeforces

 

문제 설명은 문제 참조 (조금 복잡해서)

 

 

모든 subarray를 살피며 'subarray의 길이 + subarray 안에서의 0의 개수'로 subarray의 value를 구해주었다.

 

 

C. Andrew and Stones

 

Problem - C - Codeforces

 

n개의 돌무더기가 있을 때 모든 돌들을 1번째, 혹은 n번째에 두려고 한다.

 

[i, j, k] (\(1 \leq i < j < k \leq n\), j번째 자리에 있는 돌 두 개를 각각 하나씩 i와 k번째 자리에 둔다)라는 operation이 가능할 때 모든 돌들을 1번째와 n번째 자리에 두는 최소의 operation 횟수를 구하여라.

 

 

\( \sum^{n - 1}_{i = 2} (stoneNum_i + 1) / 2 \) 로 최소 횟수를 구하였다. 불가능한 상황을 고려해주었는데, n이 3일 때에는 2번째 자리가 odd인지를, n이 4 이상일 때에는 중간의 돌들의 개수가 모두 1인 경우를 체크하였다.

 

답이 int 범위를 벗어날 수 있다.

 

 

D. Yet Another Minimization Problem

 

Problem - D - Codeforces

 

두 array a와 b가 있다. array 각각의 cost는 \(\sum^n_{i = 1} \sum^n_{j = i + 1} (a_i + a_j)^2\) 로 구한다.

 

\(a_i\)와 \(b_i\)를 swap 하는 operation이 몇 번이든 가능할 때, 두 array의 cost 합의 최솟값을 구하여라.

 

 

cost를 풀어서 i번째 원소에 대한 식으로 정리하여 swap 하였을 때 cost가 더 줄어든다면 swap을 하는 greedy 한 방식을 떠올렸는데 틀렸다...

 

풀이를 찾아보니

$$ \sum^n_{i = 1} \sum^n_{j = i + 1} (a_i + a_j)^2 $$

$$ = \sum^n_{i = 1} (n - 1)a_i^2 + (s_a - a_i) a_i \text{ (for } s_a = \sum_{i = 1}^n a_i) $$

$$ = \sum_{i = 1}^n (n - 2)a_i^2 + s_a a_i $$

$$ = (n - 2) \sum_{i = 1}^n a_i^2 + s_a^2 $$

으로 cost가 정리된다.

 

cost의 합은 \( (n - 2) \sum_{i = 1}^n (a_i^2 + b_i^2) + s_a^2 + s_b^2 \) 정도로 정리될 것이다.

 

앞의 term인 \( (n - 2) \sum_{i = 1}^n (a_i^2 + b_i^2) \) 부분은 이미 정해져 있다.

 

남은 것은 \( s_a^2 + s_b^2 \) 부분인데 이 부분을 dp를 이용하여 모든 가능한 \( s_a \)를 살펴보며 최솟값을 찾으면 된다. (\( s_a \) 값이 정해지면 \( s_b \)의 값도 정해지는 것을 이용)

 

 

풀 수 있는 문제였는데 식을 더 풀 생각을 하지 못한 게 아쉽다.

 

 

E. Best Pair

 

Problem - E - Codeforces

 

임의의 수 \(x\)의 개수를 \(cnt_x\)라 하고 \(f(x, y) = (x + y) * (cnt_x + cnt_y)\)라 정의하자.

 

n개의 수가 주어졌을 때 여기서 가장 큰 \(f(x, y)\)의 값을 구하라.

 

이 때 m개의 pair가 주어지고, 그 pair들은 사용할 수 없다.

 

 

naive하게 생각했을 때 당연히 모든 pair들을 탐색해야 함으로 \(O(n^2)\)이 걸린다. 

 

거기다 m개의 pair까지 확인해주어야한다.

 

못풀었지만 답은 간단했다. distinct한 k개의 수가 주어져있다고 한다면 \(cnt_1 + cnt_2 + ... + cnt_k = n\)을 만족할 시에 k의 기대값은 \(\sqrt{n}\)이다.

 

map을 만들어 key를 \(cnt_x\)로, value를 \(x\)로 넣어주고 만약 map에 이미 있다면 더 큰 수를 넣어준다.

 

결국 \(O(n)\) 만큼만 비교하면 되는데 m개의 pair를 고려해주어야 한다.

 

대충 map이나 set같은 것에 넣어줘서 처리한다고 하면 \(O(n\log{n})\)정도의 시간이 걸릴것이고 이 pair를 못쓰는지 확인하는것도 \(O(n\log{n})\) 만큼 걸리니 \(O(n\log{n})\)에 풀 수 있는듯.