APIO 15 Prob 1. Bali Sculptures

답을 이진수로 표현했을 때 높은 자리부터 하나하나 맞춰나가는 느낌은 어떨까?
답이 \(2^{k}\) 미만이 될 수 있게 할 수 있는지 확인해보자. (1<<\(k\) 자리가 0이 될 수 있는지)
그러려면 쪼갠 모든 구간들의 합들에 대에서 \(k\)번째 bit가 \(0\)이어야 한다.

구간 갯수에 하한이 없다면(\(A=1\)인 경우) DP로 해결할 수 있다.
앞에서 맞춰놓은 자릿수를 포함하도록 설계하면
\(dp[i] = \) 모든 구간합에서 원하는 조건이 만족되도록 \(i\)번째 원소까지를 나눴을 때 필요한 구간의 최소 갯수
로 생각할 수 있다.
이 때 원하는 조건은 \((k+1)~\)의 bit들은 앞에서 결정한 것을 만족하고, \(k\)번째 bit가 \(0\)이 되는 것을 의미한다.

'앞에서 결정한 것'이 확실한가에 대해 헷갈릴 수도 있다.
앞의 어떤 위치에 0을 결정했다면, 이 자리에는 1이 와서는 안 된다. 앞에서 0을 골랐다는 것은 그 자리에 0이 들어갈 수 있는 조합이 분명 있다는 뜻이다. 따라서 그 자리에 1이 온 경우는 무시해도 된다.
앞의 어떤 위치에 1을 결정했다면, 그 자리에 0이 들어가는 조합은 불가능하다고 이미 앞에서 못박았기 때문에 불가능하다.

즉 \((k+1)\) 이상의 bit들에 대해 bitmask를 결정하였다면, 그 bitmask에 0이 있는 자리에 대해서 \(S[i]-S[j]\)의 그 위치의 bit도 0이 되어야 하므로,
\((S[i]-S[j]) \& (\textrm{~} mask) \& (\textrm{~} ((1<<k) - 1)) = 0 \)이 되는 경우 \(i\)의 \(dp\)값을 갱신해줄 수 있다.

특정 bit에 대해, 모든 \(i\)와 \(j\)에 대해서 반복시켜주면 \(O(N^{2})\)의 시간으로 \(dp\) 배열을 채울 수 있다.
\(dp[n]\)값에 하한이 없으므로 \(dp[n] \leq B\)인가를 확인하고, 그에 따라서 \(k\)번째 bit를 결정하면 된다.
모든 bit들에 대해서 계산해주면, 모든 값의 합이 \(\Sigma\)일 때 \(O(N^{2} log \Sigma)\)의 시간이 걸릴 것이다.

구간 갯수에 하한이 있다면?
즉 \(dp[n]\)이 \(A\)보다 작은 경우 문제가 된다.
\(dp[n]\)의 정의를 '필요한 구간의 최소 갯수'로 정의했기 때문에, 하한이 있는 경우는 사용할 수 없다.
그러나 비슷한 정의로 냅색을 하듯이 할 수 있지 않을까?

\(dp'[i][j] = \) 모든 구간합에서 원하는 조건이 만족되도록 \(i\)번째 원소까지를 \(j\)개의 구간으로 나눌 수 있는가?

이 표를 채우는 데에는 얼마의 시간이 필요할까?
\(dp'[n][A]\) ~ \(dp'[n][B]\)를 구해야 하므로, \(O(N^{2})\) 공간복잡도의 \(dp'\) 배열을 채워야 한다.
위에서 설명한 규칙을 통해 \(dp'[i][j]\)를 \(dp'[t][j]\)들로 구하면 \(O(N^{3})\)의 시간이 걸리고, 모든 bit들에 대해서 수행하면 모든 값의 합이 \(\Sigma\)일 때 \(O(N^{3} log \Sigma)\)의 시간이 걸린다.

마지막 두 개의 TC가 위의 두 방법을 사용하면 해결된다.