分散は2乗の平均から平均の2乗を引いたものです。正確には、\(i\) 袋目のグッズの重さの合計を \(x_i\) としたとき、求める値は \(\frac{1}{D}\sum x_i^2-\left(\frac{1}{D}\sum x_i\right)^2\) です。

ここで \(x_i\) の定め方によらず \(\sum x_i=W_1+\ldots+W_N\) であることから、第2項 \(\left(\frac{1}{D}\sum x_i\right)^2\) は \(x_i\) の取り方によらない定数であり、第1項 \(\frac{1}{D}\sum x_i^2\) の最小化のみを考えれば十分です。

（残りのパートは公式解説と同じです）

\(\sum x_i^2\) の最小値は、次に定めるDPの \(\mathrm{DP}[D][\{1,2,\ldots,N\}]\) として求められます。

\(\mathrm{DP}[1][S]=\left(\sum_{i \in S}W_i\right)^2\)

\(\displaystyle \mathrm{DP}[k+1][S]=\min_{\emptyset \neq T \subsetneq S} (\mathrm{DP}[1][T]+\mathrm{DP}[k][S\setminus T])\)

このDPは \(\mathrm{DP}[k][*]\) から \(\mathrm{DP}[k+1][*]\)を求めるのに \(O(3^N)\) 時間かかるため、\(\mathrm{DP}[D][\{1,2,\ldots,N\}]\) は \(O(D 3^N)\) 時間で求まります。

DPの気持ちは、\( \mathrm{DP}[k][S]\) を「グッズ \(S\) を \(k\) 個の袋に分けるときの、袋の重さの2乗和の最小値」として、\(k+1\) 番目の袋に入れるグッズの集合 \(T\) を全探索するものです。

なお、答えを求める際、\(\frac{1}{D}\mathrm{DP}[D][\{1,2,\ldots,N\}]-\left(\frac{1}{D}\sum W_i\right)^2\) とそのまま計算すると浮動小数点数演算の誤差によりWAになります。 \(\frac{1}{D^2}(D*\mathrm{DP}[D][\{1,2,\ldots,N\}]-\left(\sum W_i\right)^2)\) としましょう。

(追記：なお、\(D*\mathrm{DP}[D][\{1,2,\ldots,N\}]\) は最大でも \(N^2 (\max W_i)^2\) 程度にしかならないため、問題の制約下では\(2^{63}\) 未満になることが示せます）

実装例(Python)
実装例(C++)