Codeforces Round #712 (Div. 2)

C번에서 엄청 말렸다. 결과는 똑떨.  아슬아슬하게 1600점 파킹했다.

학기 시작하고 PS를 자주 못하니 실력이 떨어지는게 눈에 보이기 시작했다.

 

A. Déjà Vu

처음 주어진 문자열이 팰린드롬이라면 정가운데를 제외하고 어디에 넣든지 팰린드롬이 아니게 된다. 주어진 문자열이 팰린드롬이 아닌데 a를 넣어 팰린드롬이 되는 경우를 생각해보면, 만약 맨 뒤에 a를 추가해 팰린드롬이 되었다면 반대로 맨 앞에 a를 추가한 경우는 전자를 왼쪽 쉬프트한 문자열이고 반대도 마찬가지다. 따라서 둘 중 하나는 무조건 팰린드롬이 아니게 된다. 따라서 처음 주어진 문자열의 맨 앞 또는 맨 뒤에 a를 추가해보고 둘 다 팰린드롬이 나오는 경우만 제외한 모든 경우가 불가능하다.

 

B. Flip the Bits

주어진 문자열을 반전시킬 수 있는 조건은 그 부분수열의 0의 개수와 1의 개수가 같아야 한다. 그런데 0과 1의 개수가 같으므로 반전시킨다고 해도 같다는 것이 보장되며, 처음 상태에서 0과 1의 개수가 같기만 하면 얼마든지 연산을 적용해도 성립함을 알 수 있다. 따라서 주어진 문자열을 뒤에서부터 확인하면서 두 문자열이 같아지도록 마음대로 뒤집으면 된다. 반전하지 못하는 경우가 생기면 실패이고, 아니면 성공이다. 뒤집어진 상태를 boolean 으로 플래그를 정해서 관리하면 편리하다.

 

C. Balance the Bits

일단 괄호 문자열의 시작점은 여는 괄호, 끝점은 닫는 괄호임이 자명하다. 따라서 두 괄호문자열의 시작점과 끝점은 동일해야 하므로 둘다 1로 표시되어야 한다. 또한 첫 번째 괄호 문자열이 성립한다고 가정했을 때 두 번째 괄호 문자열도 성립하려면, 첫 번째 괄호 문자열에서 짝수 개의 괄호가 바뀌어야 한다. 따라서 주어진 수열에 1과 0이 모두 짝수 개 등장해야 한다. 이 조건을 만족하면 모두 성립한다.

괄호 문자열을 construct하는 방법은, 첫 번째 괄호 문자열을 ()()()... 이런 식으로 정한다. 두 번째 괄호 문자열은 첫 번째에 맞춰서 정한다. 두 개씩 끊어서 하나로 보고, 두 번째 문자열이 성립하지 않으면 반전시키고 첫 번째 문자열도 함께 반전시킨다. 이렇게 되면 첫 번째 괄호 문자열은 () 또는 )(로만 이루어지는데 이는 항상 성립하는 형태이다.