Codeforces 449D. Jzzhu and Numbers

RTG3A로 만난 문제이다.

 

풀이

모든 가능한 subsequence를 다 보는 가장 간단한 브루트포스는 \(O(n\cdot 2^n)\)이다. 팀연습 중엔 여기까지밖에 생각을 못했고, 에디토리얼을 보고 내가 이해하기 편한 식으로 풀이를 한번 풀어서 써보았다.

 

우선 아래의 토의를 위해 \(a_i\)의 비트 개수를 \(m\)이라 하자. 즉, 이 문제에서는 \(m = 20\). 

 

먼저 \(a_i = 0 \text{ or } 1\)인 케이스를 생각해보자. 즉 \(a\)는 bitstring of length n. 이 상황에서 bitwise and가 0이 되는 경우의 수를 찾을려면, 먼저 0인 숫자가 하나라도 subsequence에 들어가면 bitwise and는 0이 된다는 것을 생각해보자. \(a\)에 1이 \(t\)개 있다고 하면, 1로만 이루어진 subsequence는 nonempty subsequence는 \(2^t-1\)개, 즉 bitwise and가 0이 되는 nonempty subsequence는 \(2^n-2^t\)개가 된다. 생각해보면 먼저 bitwise and가 nonzero인 subsequence를 구한다. 어처피 하나를 구하면 다른 것도 바로 구할 수 있음으로, bitwise and가 0인 subsequence개수 대신 nonzero인 subsequence개수를 구해보자.

 

이제 숫자 하나에 비트 여러개가 있는 경우를 생각해보자. 잘 생각해보면, bitwise and한 결과의 비트 중 하나만 nonzero이면 되고, 각 비트는 독립적으로 and가 된다. 즉, 각 비트마다 그 비트만 봤을때 nonzero결과값을 가지는 subsequence의 set을 가지고 있다고 생각하면, 결국 그 셋들의 union의 크기를 구하는 거니까, inclusion-exclusion principle이 자연스럽게 도입된다.

 

그러면, 대략 이런 식을 세워볼 수 있다.

bitwise and가 nonzero인 subseq개수 = \sigma{비트 1개를 봤을 때 bitwise and가 모든 비트에서 nonzero인 subseq개수} - \sigma{비트 2개를 봤을 때 bitwise and가 모든 비트에서 nonzero인 subseq개수} + \sigma{비트 3개를 봤을 때 ... }

 

어떤 비트를 보는지는 m길이의 bitstring으로 나타낼 수 있고, 각 bitstring에 대해 해당 비트를 봤을 때 [bitwise and가 모든 비트에서 nonzero인 subseq 개수 구하기] == [그 비트들을 봤을 때 모두 1인 숫자의 개수 구하기] 니까(숫자의 개수를 찾아야 subseq개수를 구하니까), 시간복잡도 \(O(n\cdot 2^m)\)에 문제를 풀 수 있다. 아직 너무 느리다!

 

우선 전전문단의 긴 우변을 합쳐서 그냥 모든 m길이의 bitmask를 보는 한 개의 시그마로 합칠 수 있다는 점을 주목하자. 순서에 상관없이 모든 m길이의 bitmask에 대해서 [bitmask에서 켜져있는 비트들에서 모두 켜져있는 숫자의 개수 구하기]를 하면 된다는 걸 생각하자. 아마 내가 전전문단 우변을 혼자 생각해냈다 하더라도 원래 순서에 묶여서 그 순서대로 계산할려고 했을것 같은데.. 여기서는 순서 상관없이 그냥 모든 bitmask에 대해서 원하는 값을 계산하기만 하면 되고, 여기서 dp의 가능성이 들어온다.

 

다음 dp식 정의를 보자.

 

dp[t][bm] = 다음 두 가지 조건을 만족하는 숫자의 a_i의 개수.

1. [0, t)번째 비트에서는, bm이 켜져있는 곳에서는 a_i도 켜져있다. 즉, bm은 a_i의 submask다. (bm&a_i = bm)

2. [t, m)번째 비트에서는, bm과 a_i가 같다.

 

우리가 원하는 건 dp[20]이다.(물론 문제의 답을 얻을려면 2^dp[20][i]를 사용해야 할 것이다.) 이 dp식은 (dp[0]이 자명하게 계산된 후) 다음과 같은 점화식을 가진다.

dp[t][bm] = bm&(1<<(t-1)) (bm의 t번째 비트가 1인가) ? dp[t-1][bm] : dp[t-1][bm] + dp[t-1][bm+(1<<(t-1))];

 

에디토리얼에서는 그냥 dp식과 점화식을 슥 하고 던져줬는데, 나는 에디토리얼을 읽은 후 개인적으로 매우 "???? 네???? 아니 여기서 저런 dp식이 어떻게 나오는거죠????" 상태에 빠져 있었다.

 

우선 이해를 위해 점화식이 어떻게 정의된 dp식을 계산하는지 추가적인 설명을 덧붙여 보자.

dp[t][bm] = bm&(1<<(t-1)) (bm의 t번째 비트가 1인가) ?

                 dp[t-1][bm] (a_i의 t번째 비트는 1인 상황만 허용할 수 있고, 따라서 dp[t-1][bm] - t-1번째 비트 전까지는 bm의 submask고 t번째 비트에서는 1인 a_i를 세자)  :

                 dp[t-1][bm] + dp[t-1][bm+(1<<(t-1))] (a_i의 t번째 비트는 0이나 1이나 상관없으니 t-1번째 케이스까지는 submask임을 만족해야한다. t-1번째 비트까지 submask고 t번째 비트에선 1인 케이스/0인 케이스를 모두 더하자);

 

이제 이 dp식의 가능한 motivation을 생각해보자. 다시 한번 떠올리자 - 우리가 원했던 것은, 모든 m길이의 bitmask에 대해서 [bitmask에서 켜져있는 비트들에서 모두 켜져있는 숫자의 개수 구하기] 이다. 자연스럽게, 어느 bitmask에 대해 그 prefix만 볼 수 있을 것이다. 딱 그렇게만 본다면 prefix를 하나 늘려나갈 때(길이 t로 늘린다고 하자), 모든 가능한 a_i의 t번째 비트를 어처피 봐야 할 것이다: a_i의 t번째 비트에 관한 정보가 dp table에 저장되어 있지 않다..! 그러한 정보를 저장하기 위해서 prefix에 대응하는 postfix에 대해 a_i의 t번째 비트 이후에 대한 정보를 어떻게든 담아야 시간복잡도를 줄일 수 있을 것이다. 위의 dp식 정의는 이러한 요구를 잘 충족시켜 하여금 t-1번째 비트 이전에는 submask에 대한 정보만 담고 있음에도 불구하고 t번째 비트 및 그 이후에는 a_i비트에 대한 description을 담고 있으니까 submask를 확장시켰을때 어느 dp값이 다음 dp값에 포함될 수 있는지를 효과적으로 판정할 수 있다.

 

에디토리얼을 읽고 그걸 내가 이해한 방식으로 풀어 썼기에 논리적 오류가 있을 수 있다. 사실 아직 inclusion-exclusion principle, dp table설계 등을 포함한 이 문제에 쓰인 개념들을 제대로 이해하지 못한 거 같다.. 쓰면서 너무 dp식정의가 신기했고, 또 너무 헷갈렸다. 아직 완전히 이해할려면 시간이 필요할 거 같다..

 

제출: https://codeforces.com/group/7YhibyVxui/contest/243605/submission/57241211