[2020-09-19] Codeforces Round 658 (Div.1)

오늘도 잘 쳤다. 약간의 실수가 아쉽지만, 이거는 할만한 실수였던 거 같다. A를 좀 더 빨리 풀만했는데 시간을 많이 써서 이것도 조금 아쉽다. D를 좀 더 고민해볼까 했는데 좀 지쳐서 그냥 문제만 읽고 컷했다. 근데 되게 재밌어 보이는 문제여서 나중에 따로 시간 잡고 풀어봐야할 듯. 큐에 넣어둬야지

A. Prefix Flip

Easy / Hard가 나뉘어 있는 문제였는데 그냥 바로 A2 풀었으니 A2를 기준으로 풀이를 쓴다. prefix를 통째로 뒤집는거니 맨 마지막 칸부터 순서대로 맞추면서 앞으로 온다고 생각하고 보자. 양쪽의 맨 오른쪽 끝 위치 칸이 같으면 그냥 한 칸씩 당겨주면 된다. 값이 다른 경우가 문제인데, 여기서 경우를 나눌 수 있다.

1. 현재 남은 구간에서 맨 왼쪽 끝 위치 값이 만들어야 하는 값과 반대인 경우 : 전체 구간을 한 번 뒤집어주면 맨 오른쪽 끝 칸을 일치시킬 수 있다.

2. 현재 남은 구간에서 맨 왼쪽 끝 위치 값이 만들어야 하는 값과 같은 경우 : 1~1 구간만 뒤집으면 1번 케이스로 환원된다.

 

따라서, 항상 최대 2번의 연산으로 맨 오른쪽 끝을 일치시킬 수 있고, 나머지 구간은 구간 전체에 대해 연산이 적용된 상태가 된다. 구간 전체에 대한 연산 적용 여부만 관리하면서 맨 왼쪽-오른쪽 끝이 무엇인지 처리해주면 답을 O(N)에 계산할 수 있다.

B. Unmerge

주어진 배열에서 k 뒤에 k보다 작은 값들이 나오면, 그 값들은 전부 k와 같은 배열에 들어가야만한다. 그렇지 않다고 가정해보자. k 보다 앞까지 전부 merge하고 난 다음 시점에서 A배열의 맨 처음에는 k가 있을 거고, B 배열의 맨 처음에는 k 다음 수들이 있을 것이다. 이 경우, B배열의 값이 더 작기 때문에 k보다 이 값이 먼저 들어가야 한다. 이렇게 되면 주어진 수열이 깨지므로, 이렇게 되어서는 안 된다. 따라서, k부터 연속해서 k 보다 작은 수들이 있는 경우 전부 묶어서 한 덩어리로 생각할 수 있다.

 

그 외의 경우는 항상 어떻게 붙여도 상관없음을 알 수 있다(merge 동작이 정렬된 순으로 넣는 것이기 때문에, 이 정렬 순이 같은 배열에서 성립하든 다른 배열에서 성립하든 상관이 없음).

 

 그러면 배열을 한 번 순회하면서 묶어서 같이 들어가야만 하는 덩어리들의 크기를 계산해줄 수 있다. 이제 이 덩어리들 중에 일부를 선택해서 합이 N이 되게 할 수 있는지 묻는 문제로 바뀐다. 이는 직관적인 O(N^2) DP로 해결할 수 있으므로 이걸 구현하면 된다. 배열 길이가 2N이라 테이블을 2N 사이즈로 잡아야하는데 이걸 실수해서 한 번 WA를 받았다..

C. Mastermind

서로 순서를 어그러뜨려야하는 집합만 놓고 봤을 때, 이 크기가 k라고 하면 개수가 k/2개보다 많은 색이 있다면 모두 겹치지 않게 재배치하는 건 불가능하다. 여기서 x개는 위치를 일치시킬 수 있으므로, 처음 집합에서 최대 x개를 제외할 수 있다. 이 때 위에 적은 조건을 최대한 만족시키려면, 같은 색을 공유하는 집합의 크기 최대를 가능한 한 작게 줄이는게 이득이다. 따라서, PQ 등을 이용해서 최댓값을 최소화하게끔 x개를 배치해준다.

 

이렇게 배치하고 나면, 나머지는 순서를 어그러뜨려야 하는게 y-x개, 아예 다른 값으로 바꿔야하는게 n-y개가 남는다. 이걸 아예 다른 값으로 바꾸는 과정은 무시하고 순서를 바꾸자. 남은 위치들을 같은 색이 인접하게끔 묶어서 1차원 배열상에 나열하면, 최댓값이 k라고 했을 때 모든 칸을 배열상에서 k번 뒤 위치의 값으로 리매핑하는게 최선이다. 이 경우, 최댓값 k가 전체 개수 절반 이하면 그냥 성립하고, 그렇지 않다면 맨끝에서 조금 겹치게 된다. 이 겹치는 개수보다 더 적게 겹치게 만들 수는 없다. 따라서, 이 겹치는 개수가 n-y보다 크다면 어떻게 해도 해결이 안되므로 NO가 답이 되고, 그렇지 않다면 그 위치를 적당히 커버해서 답이 성립하게 만들 수 있다. 따라서 O(NlogN)에 문제를 해결할 수 있다.

 

풀이 스케치는 엄청 일찍 나왔는데, 정확한 방법을 생각하는데 시간을 너무 많이 썼다. 이런 거 좀 더 빨리 잘 정리해서 풀 수 있었으면 좋겠다.