UCPC 2024 예선에 출제한 문제이다. 검수 과정에서 아주 다양한 풀이가 등장하여 이 글에서 모두 공유해보고자 한다.

공통 관찰

먼저, 두 개의 동전을 뒤집으면 홀수 자리의 T와 짝수 자리의 T의 개수가 각각 동시에 1 증가하거나 1 감소한다. 따라서 둘의 개수가 다르면 모두 H로 만들 수 없어 답은 불가능이 된다.

앞으로 다룰 모든 풀이는 동전을 모두 H로 만들 수 있다고 가정한다.

에디토리얼 풀이

주어진 문자열의 모든 prefix에 대해 홀수 자리의 T의 개수와 짝수 자리의 T의 개수의 차의 절댓값을 계산한다. $i$번째와 $i+1$번째 동전을 뒤집는 조작을 하였을 때, 다음과 같은 일이 일어난다.

  • 길이 $i$ 미만의 prefix에 대한 값은 변하지 않는다. 어느 동전도 뒤집히지 않았기 때문.
  • 길이 $i$의 prefix에 대한 값은 1 증가하거나 1 감소한다. 뒤집힌 두 동전 중 하나만 반영되기 때문.
  • 길이 $i$ 초과의 prefix에 대한 값은 변하지 않는다. 뒤집한 두 동전이 모두 반영이 되는데, 하나는 홀수 번째, 다른 하나는 짝수 번째이고, 둘의 보이는 면이 같으므로 둘 다 1 증가하거나 1 감소하여 두 값의 변화가 상쇄된다.

따라서, 어떤 시행을 하더라도 이러한 값의 총합은 1 증가하거나 1 감소한다. 모두 H인 문자열에서 이 값은 0이므로, 적어도 입력 문자열에서의 값만큼의 조작이 필요하다.

어떠한 상태에 있더라도 한 번의 시행으로 총합을 1 감소시키는 방법이 존재함을 보일 수 있으며, 따라서 이 값이 답이 된다.

에디토리얼 별해 1 (괄호 문자열 기반 풀이)

THH...HT라는 부분 문자열이 있다고 해보자. 여기서 두 개의 T의 위치의 홀짝이 다르면, H를 한 쌍씩 모두 뒤집은 다음 T를 한 쌍씩 뒤집어서 두 개의 T를 “제거” 할 수 있다. 홀짝이 같으면 제거할 수 없다. 두 T를 제거하는 데에는 정확히 두 위치의 차이만큼의 조작이 필요하다.

따라서, 홀짝이 다른 T끼리 매칭하여 제거하는 풀이를 생각해볼 수 있다. 홀홀짝짝이면 안쪽의 홀짝을 제거한 후 바깥쪽의 홀짝을 제거하는 것이 유일한 방법이고, 홀짝홀짝이면 양쪽의 홀짝끼리 매칭해주는 것이 최적이므로, 괄호 문자열 매칭해주듯이 그리디하게 매칭하는 것이 최적일 것이라고 예상할 수 있다.

이 풀이의 엄밀한 증명은 시도해보지 않았으나, 에디토리얼 풀이의 합을 다르게 카운팅하면 괄호 문자열 매칭이 나오는 것으로 보인다.

대회 중에 생각해내기 가장 쉬운 풀이로 예상되었으며, 실제로 그렇게 많이 풀린 것으로 보인다.

에디토리얼 별해 2 (XOR 기반 풀이)

짝수 번째 동전을 모두 뒤집고, 가능한 조작을 다음과 같이 바꾼다.

  • 두 이웃한 동전이 서로 다른 면을 보일 때 두 동전을 뒤집는다.

그러면 원래 문제의 조건에서 뒤집을 수 있는 위치와 새로운 상황에서 뒤집을 수 있는 위치가 모두 일치한다. 또한, 서로 다른 면이 보이는 이웃한 두 동전을 뒤집는 것은 T를 이웃한 H로 한 칸 이동하는 것으로 볼 수 있고, HHHHHH...인 최종 상태는 HTHTHT...로 바뀐다. 따라서, 새로운 조건에서의 T들을 최소한의 횟수로 움직여 모두 짝수 번째 자리에 놓는 문제로 환원이 되며, 이는 매우 쉽게 풀 수 있다.

이 풀이를 알고 있는 사람들 사이에서는 010101...로 XOR하는 풀이로 알려져 있는 듯하다. 이러한 풀이가 사용되는 다른 문제로 15941. TV 동물 농장, 18346. 업과 격의 그래프 등이 언급되었는데, 15941이 공교롭게도 UCPC 기출이어서 대회에서 빠질 뻔했다.

검수진 풀이 1

먼저, 문자열 $S$를 $T$로 바꾸기 위한 최소 조작은 두 문자열의 공통 접두사를 조작하지 않으며, 처음으로 다른 문자가 $i$번째라면 $i$번째와 $i+1$번째 동전을 뒤집는 조작을 정확히 한 번 시행하여 $S$에서 $T$로 갈 수 있음을 보일 수 있다.

이를 이용하여, $i$번째 동전을 보고 $i+1$번째 동전이 거쳐야 하는 중간 상태들을 기록하고 그에 필요한 조작의 횟수를 모두 더하여 답을 얻을 수 있다. 예를 들어 입력이 THTTHT라면 다음과 같이 계산한다.

  1. T: T -> H가 1회 발생한다. ans += 1
  2. H: H를 먼저 T로 한 번 바꿔야 첫 번째 문자의 시행 T -> H를 할 수 있다. ans += 1 (H -> T)
  3. T: 두 번째 문자의 시행 H -> T를 하기 전에 T -> H가 한 번 일어나야 하고, 그 뒤에 다시 H로 바꿔야 하므로 총 2회의 추가 조작이 발생한다. ans += 2
  4. T: 세 번째 문자의 시행(T -> H, T -> H)을 하기 위해서는 중간에 H -> T를 추가로 한 번 해야 한다. ans += 1
  5. H: 네 번째 문자의 시행(H -> T)을 한 후 T를 다시 H로 바꿔야 한다. ans += 1
  6. T: 다섯 번째 문자의 시행(T -> H)을 하면 추가적인 조작은 필요 없다.

따라서 정답은 6이 된다.

각 위치에서 추가로 필요한 조작은 T -> H, H -> T 중 한 종류만 필요함을 알 수 있으며, 이전 위치에서 사용한 조작을 보고 현재 위치에 필요한 조작의 종류와 횟수를 구해서 더하면 된다.

각 위치에서 ans에 더해지는 값은 에디토리얼 풀이와 일치한다.

검수진 풀이 2

이 풀이도 가장 왼쪽의 T가 $i$번째에 있으면 $i$번째와 $i+1$번째 동전을 정확히 한 번 뒤집어야 함을 이용한다.

이 관찰을 확장하여, 맨 왼쪽의 T에서 시작하여 THTHTH...THH 또는 THTHTH...TT 형태의 부분 문자열이 존재하면 맨 오른쪽부터 왼쪽 방향으로 순서대로 뒤집어서 맨 왼쪽의 T를 제거하는 것이 최적해에 포함되도록 할 수 있음을 보일 수 있다. 이 조작을 마치면 해당 구간의 맨 왼쪽의 T와 맨 오른쪽의 동전만 뒤집한 상태로 바뀌며, 이는 그 다음 T에서 시작하는 THTH... 패턴이 된다. 따라서 맨 처음 등장하는 T를 유지해가면서 동전을 2개씩 뒤집고 구간의 길이를 더해 나가는 투 포인터 풀이를 얻을 수 있다.

검수진 풀이 3

앞에서부터 보면서 각 동전을 반드시 뒤집어야 하는 횟수를 관찰해 본다.

  • 처음 등장한 T는 1번 뒤집어야 한다.
  • 홀수 개의 T 뒤에 등장하는 H는 2번 뒤집어야 한다.
  • 홀수 개의 T 뒤에 홀수 개의 H 뒤에 등장하는 T는 3번 뒤집어야 한다.

이렇게 앞에서부터 홀수 번 나온 문자를 스택으로 관리하여 각 동전을 뒤집어야 하는 횟수를 모두 더하고, 한 번의 조작으로 동전이 2개씩 뒤집어지므로 2로 나눠서 정답을 얻을 수 있다.