概要
2023年12月10日(日)に開催されたABC332の解説(といいつつ公式解説の補足がメイン)。
問題
本文
- $N$個のグッズがあり、それぞれの重さは $W_i (1 \leq i \leq N)$である。
- これらのグッズを $D$個以内の袋に仕分けたい。「以内」なので、グッズが入っていない袋が存在してもよい。但し、袋に入っていないグッズは存在してはならない。
- 袋ごとのグッズの重さの合計を$x_1, x_2, \ldots ,x_D$としたとき、平均$\bar{x}=\frac{1}{D}\left(x_1+x_2+ \ldots +x_D\right)$, 分散$V=\frac{1}{D}\sum\limits_{i=1}^D \left(x_i - \bar{x} \right)^2$で定義される分散$V$の最小値を求めよ。
制約
- $2 \leq D \leq N \leq 15$
- $1 \leq W_i \leq 10^8$
解説
問題を一目見て、直感的にその時点で袋に入れているグッズの集合と何袋に分けたかの2次元で管理するbitDPができそうと感じる。制約の小ささや、どの順番でグッズを袋に入れても最終的に袋に入っているグッズの構成が同じなら結果が変化しないことが、そう考える根拠。
しかし、大きな問題がある。それは、単に分散を最小化しようとすると、各時点での各袋の重量の平均が変化するという点。分散の定義に出てくる項のうち、各袋に入っている重さの合計の二乗和は最小化できるが、平均の方が問題。
ここで、この問題の重要なポイントの一つは、$\bar{x}$が定数であること。なぜならば、必ずすべてのグッズが袋に入っていなければならないという問題の条件から、$\bar{x}=\frac{1}{D}\left(x_1+x_2+ \ldots +x_D\right) = \frac{1}{D}\left( W_1 + W_2 + \ldots + W_N \right)$ が成り立つため。
したがって、各時点での各袋のグッズの重さの合計から$\bar{x}$を差し引いたものの二乗和の最小値に対してbitDPを考えれば、最後に全グッズを$D$袋に分けたときのDPの値を$D$で割ることで、分散$V$が求まる。
ここまでわかれば話は簡単で、詳細は公式解説に譲るが、
$S$をこれまでに袋詰めしたグッズの添字の集合、$k$を$k$袋に分けるとして$DP[S][k]$をその時の各袋の重さの合計から$\bar{x}$を差し引いたものの二乗和の最小値として、bitDPを考えれば、$DP[all_S][D]$($all_S$はグッズ$N$個の添字からなる全体集合)を見ることで分散が計算できるようになる。
DPの初期化は、1袋に詰める場合、すなわち$DP[S][1]$($S$は$all_S$の任意の部分集合)から始める。この時、$S$のすべてのグッズを1袋に詰めるので計算は簡単で、$DP[S][1]=\left(\sum\limits_{s \in S} W_s-\bar{x}\right)^2$ となる。
ここからは$k=2,3,\ldots,D$と順に遷移するが、この際には$DP[S][k]=\min\limits_{T \subseteq S}(DP[S-T][k-1]+DP[T][1])$とすればOK。ここで$S-T$は差集合を意味する。
この遷移のお気持ちは、グッズの集合$S$を$k$袋に分けるときには、部分集合$T$を避けて$k-1$袋に分ける場合と、弾いた$T$を1袋に入れた場合を加算するという意味。これを部分集合全体にわたって計算し、最小値で更新する。
$k-2$袋と2袋に分ける場合などを考える必要はないのか？ともなるが、$k-2$袋に分けたときの最小値は$k-1$袋に分けるときへの遷移で既に反映されているので、$k-1$だけ考えておけば大丈夫。
最後に、数値誤差に気を付けつつ $DP[all_S][D]/D$にあたる値を出力すればよい。
DPの初期値の設定はどうするの？
上記は公式解説にも記載されている内容。ただ、公式解説には、DPの初期値をどう設定すべきかが文面からはわかりづらい。具体的には$DP[0][1]$をどう設定すべきか？という点。これはすなわち0個のグッズを1袋に分けることを意味するが、この問題ではグッズの入っていない袋を許容するため、グッズの重さの和が0の袋が1つあると考え、$DP[0][1]=(0-\bar{x})^2$とすればよい。
冷静に考えればこれでしかないが、DPを用いて最小値を計算するような問題では、最初にDPの全体を巨大な数字で初期化してあげることも多いので、このあたりの初期値設定などは注意して行わねばならないと感じた。今回は、0個のグッズが$d$袋を占めているとき、残り$N$個のグッズを$D-d$袋に分配してあげる必要がある。つまり、グッズが入っていない袋にも意味があるので、適当な値で初期化するのは妥当ではないということになる。普段最小値を求めるDPで盤面を巨大な値で初期化していいのは、それが問題設定の中で実現不可能だから。何も入っていない袋の重さを0として扱う以上、それに適した値を設定する必要がある。