CodeForces Round 961(Div. 2) D

문제 요약
알파벳의 첫 c개의 문자로만 이루어진 길이 N짜리 문자열이 주어진다(c=2라면 A와 B로만 이루어진 문자열, c는 18이하, N은 2^18이하). 각각의 단어의 case는 해당 단어가 어떤 글자로 끝났는지에 따라 결정된다. 각 단어의 길이가 최대 K개일 때, 주어진 문자열이 단어들을 띄어쓰기 없이 나열한 것이라면 해당 단어 집합에서 나올 수 있는 최소 case의 개수를 구하여라.

풀이
일단 딱 봐도 비트마스킹 DP라는 생각은 빠르게 든다. DP[i][state]=i번째 문자까지 봤을 때, state로 표시된 문자를 case로 삼을 수 있다면 1, 아니라면 0으로 놓고 풀면 O(N*2^c)안에 돌아가는 프로그램을 짤 수 있다.

하지만 이건 너무 느리다. 2^36은 너무 큰 숫자이다. 여기서 최적화를 하기 위해 해야 하는 발상이 참신하다. 나는 대회 때 이걸 못 해내서 레이팅이 많이 떨어졌다...ㅠㅠ

먼저 문제를 다시 생각해보면, 일단 문자열의 끝 문자는 항상 case가 되어야 할 것이고, 모든 길이가 K인 부분문자열들이 적어도 하나의 case는 포함해야 할 것이다.

각각의 길이 K인 부분문자열을 i번째 문자를 포함하면 1, 그렇지 않다면 0으로 나타내는 이진 수열로 나타내보자. 우리가 찾아야 하는 case가 켜진 이진 수열은 이 이진 수열들 중 어떤 것과 and 연산을 하더라도 0이 되어서는 안된다. 대회 중에 여기까지는 생각을 했는데 이걸 찾는 것을 아무리 생각해도 빠르게 할 수가 없었다.

방법은 다음과 같다. 발상을 조금 틀어서, case를 나타내는 이진 수열 중 가능하지 않은 것을 걸러내는 것이다. 이는 각 길이가 K인 부분문자열을 나타낸 이진 수열을 (2^c)-1과 xor연산을 한 것의 서브마스크에 해당할 것이다. 따라서 문제를 O(N)개의 이진 수열의 서브마스크를 구하는 문제로 바꿀 수 있고, 이는 O(2^c*c)안에 가능하다.(냅색을 하는 느낌으로 큰 값부터 결정하면서 해당 이진 수열에서 하나의 비트만 켰을 때 포함되어 있는지를 보는 식으로 하면된다)

따라서 이렇게 불가능한 것들을 거르고, 가능한 것들 중 pop count가 가장 작은 것의 pop count를 출력해주면 답을 구할 수 있다.

이런 식으로 답을 구할 생각은 못했는데, 상당히 중요한 아이디어인 것 같다. 이 게시물을 틈틈이 정독하면서 리마인드 하도록 하자.