ARC096 F : Sweet Alchemy(900)
作成日：2018.09.16
最終更新日：2018.09.16
問題概要
$1$から$N$まで番号が振られた$N$種類のドーナツがあり、ドーナツ$i$を$1$個作るのに材料が$m_i$グラム必要である。
またドーナツ$i$($\geq 2$)のレシピはドーナツ$p_i$($\lt i$)のレシピを改変したものである。
材料が$X$グラムある時、条件「ドーナツ$i$($\geq 2$)を作る個数$c_i$は$c_{p_i} \leq c_i \leq c_{p_i} + D$となる」を満たすように作ることのできるドーナツの総数を求めよ。
但し材料は余っても良いが、各ドーナツは整数個作るものとする。
制約
$2 \leq N \leq 50$
$1 \leq X \leq 10^9$
$0 \leq D \leq 10^9$
$1 \leq m_i \leq 10^9$
$1 \leq p_i \lt i$
考え方
ドーナツを作る個数の制約が厄介なので、これについて考える。
$c_{p_i} \leq c_i$であるから、ドーナツ$p_i$を$1$個作ると同時にドーナツ$i$も$1$個作るとして良い。
これを繰り返し適応していくと、ドーナツ$p_{p_{...p_i}}$を$1$個作ると同時にドーナツ$i$も$1$個作るとして良いことが分かる。
すなわちドーナツを頂点とすると、頂点$1$を根とし頂点$i$は頂点$p_i$を親とするような根付き木において、頂点$i$に対応するドーナツを$1$個作る時はその頂点を根とする部分木に含まれる頂点に対応するドーナツもそれぞれ$1$個作るということになる。
そこで各頂点において、その頂点$i$に対応するドーナツを$1$個作る時に作ることとなるドーナツの個数$v_i$及びそのために必要な材料$w_i$を考え、ドーナツを作る代わりに頂点を重複込みで選ぶことにする。
$0 \leq c_i - c_{p_i} \leq D$であるから、頂点$1$以外の頂点を選べるのは$D$回以下である。
また選ぶ回数の下限は存在しないから、これは重さ$w_i$、価値$v_i$をもつ荷物をつめるナップサック問題に帰着できたことになる。
このナップサック問題の制約は、種類数$N \leq 50$、容量$X \leq 10^9$、$w_i \leq N \times 10^9$、$v_i \leq N$、($i \neq 1$において)同じ荷物を選べる回数$D \leq 10^9$である。
これは容量も大きく、価値の総和も大きくなりうるから、DPだけでは解を求められない。
$2$つの頂点$i,j$のみを取り出して、$V = c_i v_i + c_j v_j$を最大化しつつできるだけ$W = c_i w_i + c_j w_j$を小さくすることを考える。
どちらをより優先的に選ぶべきかを知るために$c$のうち片方を$0$とする。
$V = v_i v_j$で固定すると$c_i = 0$の時$W = v_i w_j$、$c_j = 0$の時$W = v_j w_i$となるから、$v_i w_j \lt v_j w_i$すなわち$v_i / w_i \lt v_j / w_j$となる時は頂点$j$を優先的に選ぶべきであると分かる。
ただ、$V \lt v_i v_j$である時にも同様であるかは分からない($V = 30$,$v_i = 6$,$w_i = 7$,$v_j = 7$,$w_j = 8$の時など)。
それでも頂点$j$がまだ$v_i$回以上選べるのに$c_i \geq v_j$となるような逆転現象は起こらない。
すなわち逆転現象が起こり得る分だけを別に計算すれば、残りは$v / w$が大きい順に貪欲に選ぶことにより答えを求めることができる。
逆転現象が起こる分は、各頂点において高々$N$回である。
だから各頂点について、選べる回数の最大値と$N$の小さい方だけ選ぶ分を計算することにする。
この部分の価値の総和は$N^3$以下、荷物は各種類$N$個以下になるから、$O(N^5)$のDPで価値の総和の値ごとに必要な容量の最小値を求められる。
$O(N^5)$はぎりぎりだが、処理は足し算をして$min$をとるだけで軽いので間に合いそうである。
後は$X-$(DPで求めた必要な容量の最小値)を容量として貪欲法を適用すれば良い。
価値の総和の値をそれぞれ試すので、貪欲の部分の計算量は$O(N^4)$である。
以上により答えを求めることができる。
ソースコード
マクロ等はこちら
int N,X,D;
LL m[55];
int p[55],z[55];
LL w[55],v[55];
LL dp[51*51*51];
int main(){
cin >> N >> X >> D >> m[0];
repp(i,1,N){
cin >> m[i] >> p[i];
--p[i];
z[i] = i;
}
repm(i,N-1,0){
w[i] += m[i];
++v[i];
w[p[i]] += w[i];
v[p[i]] += v[i];
}
w[0] += m[0];
++v[0];
fill(dp,dp+N*N*N+1,X+1);
dp[0] = 0;
repp(i,0,N) repp(j,0,i?min(N,D):N) repm(k,N*N*N,-1) dp[v[i]+k] = min(dp[v[i]+k],w[i]+dp[k]);
sort(z,z+N,[&](const int &a , const int &b){return w[a]*v[b] < w[b]*v[a];});
int ans = 0;
repp(i,0,N*N*N+1) if(dp[i] <= X){
int r = X-dp[i] , n = i;
repp(j,0,N){
int m = min(r/w[z[j]],(LL)max(0,z[j]?D-N:X));
r -= m * w[z[j]];
n += m * v[z[j]];
}
ans = max(ans,n);
}
cout << ans << endl;
return 0;
}解法まとめ
ドーナツを頂点とみなし、$i$と$p_i$が辺で結ばれているような頂点$1$を根とする根付き木において、$v_i=$(頂点$i$の部分木に含まれる頂点数)、$w_i=$(頂点$i$の部分木に含まれる頂点に対応するドーナツの$m$の総和)とする。
これにより重さ$w_i$、価値$v_i$をもつ荷物を$i = 1$は無制限に、$i \geq 2$は$D$個までつめられるナップサック問題に帰着される。(14-21行)
各荷物$min(N,D)$個($i = 1$では$N$個)まで使えるとし、価値の総和の値($0$から$N^3$まで)を状態として持つDPで、それぞれの値における必要な容量の最小値を求める。(22-24行)
DPで使えるとしなかった分の荷物を$v_i / w_i$が大きいものから貪欲に選んでいく。これをDP部分で求めた価値の総和の値$V$それぞれにおいて容量を$X-dp[V]$として行う。
貪欲に選んだ部分の価値の総和に$V$を加えた値のうち最大のものが答えとなる。(25-36行)