Codeforces Round #732 (Div. 2)

A번이 약간 말려서 당황했는데, 그래도 B, C가 잘 풀려서 다행이었다. 4솔도 노려볼 만했는데 더 풀지는 못해서 아쉽다.

 

A. AquaMoon and Two Arrays

두 수열이 주어지고 한 수열에 적절히 연산을 하여 두 수열이 같게 만들어야 한다. 일단, 연산을 해도 각 수열의 합은 보존되므로 두 수열의 합이 다르다면 무조건 불가능하다. 두 수열의 각 원소의 차를 구하고, 그 차가 0 초과인 원소를 0 미만인 원소에 옮겨주면 된다.

 

B. AquaMoon and Stolen String

n개의 문자열에서 한 개의 문자열을 없앤 뒤 남은 n-1개의 문자열을 섞는다. 이 때 없어진 문자열을 찾는 문제이다.n-1개의 문자열을 섞을 때 같은 열의 두 원소 즉, 문자열 S와 T가 있다면$S_i$ 와 $T_i$를 바꾼다. 따라서 각 열에 대하여 알파벳의 등장 횟수는 보존된다. 초기상태인 n개의 문자열에 대하여 각 열에 등장하는 알파벳의 수를 계산해두고, 섞인 n-1개의 문자열이 주어졌을 때, 각 열에 해당하는 알파벳의 수를 계산하면 사라진 알파벳 한 개를 찾을 수 있다.인터랙티브 문제인데 왜 인터랙티브인지 모르겠다.

 

C. AquaMoon and Strange Sort

버블정렬의 특성을 활용한 문제이다. 주어진 수열이 정렬되었을 때, 모든 원소가 처음 위치에서 이동한 거리가 짝수가 되어야 한다. 같은 수가 등장할 수 있기 때문에 이들을 적절히 재배치하는 것이 관건이다.

map을 사용하여 짝수 번째 위치에 나타나는 수와 홀수 번째 위치에 나타나는 수를 각각 센다. 정렬 한 후에 다시 짝수 번째 위치에 나타나는 수와 홀수 번째 위치에 나타나는 수를 센다. 두 상태에서 센 수가 같다면 ok이다. 이는 짝수 번째 위치에서 다시 짝수 번째 위치로 이동하고, 홀수 번째 위치에서 다시 홀수 번째 위치로 이동했기 때문에 조건을 만족한다. 반대로 두 상태에서 센 수가 다르다면 짝수 번째 위치에서 홀수 번째 위치로 이동하거나, 홀수 번째 위치에서 짝수 번째 위치로 이동한 수가 있다는 뜻이므로 불가능한 경우이다.