IOI2020 Day2 biscuits 풀이

문제 및 채점: oj.uz

 

$K$ 개 종류의 비스킷이 있고, 각 종류는 번호가 1부터 $K$까지 매겨져 있다. $i$번 종류의 비스킷의 맛 점수는 $2^{i-1}$이며, $i$번 종류의 비스킷은 $a[i]$ 개 있다. 비스킷 일부를 선택하여 비스킷 바구니 $x$ 개에 나눠 담을 건데, 각 비스킷 바구니에 담긴 비스킷 맛 점수의 합을 동일하게 해야 한다. 이렇게 나눌 때 만들 수 있는 바구니에 담긴 비스킷 맛 점수의 합의 수를 구하는 문제다.

 

다음과 같은 DP 배열을 정의하자.

$$D[i] = \text{1번부터 }i\text{번 비스킷까지 사용했을 때 만들 수 있는 합의 수}$$

초기값은 $D[0] = 1$이 된다.

 

$i$ 번 비스킷까지 사용하여 만들 수 있는 합 중 가장 큰 수를 $b$라고 하자. 그러면 아래 점화식으로 $D[i]$를 계산할 수 있다.

$$D[i] = \biggl(\sum{D[j]}\biggr) + 1\ \bigl(b\text{의 }j\text{ 비트가 1인 모든 }j\text{에 대해}\bigr)$$

예를 들어, $i = 8$이고, $b = 41 = 101001_{(2)}$인 경우에 대해 $D[i]$ 값 계산 점화식이 어떻게 동작하는지 확인해보자. $b$의 비트 중 1인 비트는 0비트, 3비트, 5비트다. 점화식에 따르면 $D[8] = D[0]+D[3]+D[5]+1$가 된다.

* $D[5]$는 만들 수 있는 합 중 이진수로 표현했을 때 $000?????_{(2)}$와 같은 꼴이 되는 합의 수를 의미한다.

* $D[3]$은 만들 수 있는 합 중 이진수로 표현했을 때 $00100???_{(2)}$와 같은 꼴이 되는 합의 수를 의미한다.

* $D[0]$은 만들 수 있는 합 중 이진수로 표현했을 때 $00101000_{(2)}$와 같은 꼴이 되는 합의 수를 의미한다.

* 마지막으로 $1$은 만들 수 있는 합 중 이진수로 표현했을 때 $00101001_{(2)}$와 같은 꼴이 되는 합의 수를 의미한다.

 

만약, 만들 수 있는 가장 큰 수 $b$가 0인 경우 바구니에 수가 들어 있지 않은 경우만 가능하므로 $D[i] = 1$이 되어, 위 점화식이 이 경우에도 유효하다. 이렇게 DP를 계산하면 시간복잡도 $O(B^2)$이 된다. 여기서, $B$는 가장 큰 수의 비트 수다.

 

#include <bits/stdc++.h> #include "biscuits.h" using namespace std; typedef long long lld; lld count_tastiness(lld x, vector<lld> a) { vector <lld> status(63, 0); lld sum = 0; for (int i=0;i<63;i++){ if (i < a.size()) sum += a[i]<<i; status[i] = sum; } vector <lld> dp(63, 0); dp[0] = 1; for (int i=1;i<63;i++){ lld cur = sum; dp[i] = 1; for (int j=i;j--;){ cur = min(cur, status[j]); if (x <= cur>>j){ cur -= x<<j; dp[i] += dp[j]; } } } return dp.back(); }