【競技プログラミング】AtCoder Beginner Contest 332_E問題

# 問題

https://atcoder.jp/contests/abc332/tasks/abc332_e

## 要約

1. AtCoder社には N 個のグッズが残っており、各グッズの重さは W_i 。

2. これらのグッズを D 袋の福袋に分けて販売する。

3. 目標は、各福袋に入ったグッズの重さの合計の分散を最小にすること。

4. 分散の定義：V = (1/D) * Σ(x_i - x̄)^2 
   ここで、x_i は各福袋の重さの合計、x̄ はそれらの平均。

5. 条件：
   - 空の福袋があってもよい（その場合、重さは0とする）
   - 各グッズは必ずどれか1つの福袋に入れなければならない

6. 求めるもの：最適な分け方をした時の分散の最小値

変数情報：
- N: グッズの総数
- W_i: i番目のグッズの重さ (1 ≤ i ≤ N)
- D: 福袋の数

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 独り言

[何時間かけても解けなかった過去挑戦Ver](https://qiita.com/o_chan_t/items/2cd55a2fc6b848d9a617)
とりあえず、青色を目標にしている以上、E問題までは着実に解ける実力は付けておきたい。
特にDP問題ってパズル要素があるので、楽しいから難問でもあまり苦にならないし。

# アプローチ

動的計画法を用いて、グッズの組み合わせと福袋の数に基づいて最適な分配を計算する。
ビット演算を活用して全ての組み合わせを探索し、各状態での最小の分散を計算する。


# 解法手順

1. 入力を受け取り、グッズの総重量の平均値を計算する。

2. 全てのグッズの組み合わせに対して、その重量の合計と平均値との差の二乗を事前計算する。

3. 動的計画法のテーブルを初期化する。テーブルのサイズは(2^N) * (D+1)とし、各状態は「使用したグッズの組み合わせ」と「現在の福袋の数」で表す。

4. 動的計画法を実行する：
   a. 全てのグッズの組み合わせ（2^N通り）についてループを回す。
   b. 各組み合わせに対して、そのサブセットを全て列挙する。
   c. 各サブセットを新しい福袋に入れた場合の分散を計算し、最小値を更新する。

5. 全てのグッズを使用し、D個の福袋を作った状態の分散を計算する。

6. 最終的な分散の最小値を出力する。


# ACコード
```python:ac.py

def solve(n,d,w):
    # グッズの総重量の平均値を計算
    x = sum(w) / d

    # ビット演算のための定数を設定
    l1 = 1 << n  # 2^n
    l2 = d + 1

    # 状態を表す関数を定義
    def f(i, j):
        return i * l2 + j

    # 全てのグッズの組み合わせに対して、重量の合計と平均値との差の二乗を事前計算
    a = [0] * (1 << n)
    for j in range(1 << n):
        s = 0
        for i in range(n):
            if j >> i & 1:
                s += w[i]
        a[j] = (s - x) ** 2

    # 動的計画法のテーブルを初期化
    dp = [float('inf')] * l1 * l2
    dp[f(0, 0)] = 0.0

    # 動的計画法を実行
    for i in range(1 << n):
        j = i
        while j >= 0:
            j &= i
            for k in range(d):
                dp[f(i, k + 1)] = min(dp[f(i, k + 1)], dp[f(i ^ j, k)] + a[j])
            j -= 1

    # 最終的な分散の最小値を計算して出力
    ans = dp[f((1 << n) - 1, d)] / d
    print(ans)

if __name__=="__main__":
    # 入力を受け取る
    n, d = map(int, input().split())
    w = list(map(int, input().split()))
    solve(n,d,w)



```

# 机上トレース(001)
## 設定値

n = 5
d = 3
w = [7, 3, 10, 10, 9]

## 想定出力

ans = 6.0

### グッズの総重量の平均値を計算

グッズの総重量の平均値: 39, 13.0

### ビット演算のための定数を設定

l1 = 32   # 2^5
l2 = 4     # d+1

### 全てのグッズの組み合わせに対して、重量の合計と平均値との差の二乗を事前計算

- a[0] = (0 - 13.0) ** 2 = 169.0 # 初期値

- a[1] = (7 - 13.0) ** 2 = 36.0 # 0個目のグッズの重さ(7)の合計7と平均値13.0との差の二乗

- a[2] = (3 - 13.0) ** 2 = 100.0 # 1個目のグッズの重さ(3)の合計3と平均値13.0との差の二乗

- a[3] = (10 - 13.0) ** 2 = 9.0 # 0個目のグッズの重さ(7),1個目のグッズの重さ(3)の合計10と平均値13.0との差の二乗

- a[4] = (10 - 13.0) ** 2 = 9.0 # 2個目のグッズの重さ(10)の合計10と平均値13.0との差の二乗

- a[5] = (17 - 13.0) ** 2 = 16.0 # 0個目のグッズの重さ(7),2個目のグッズの重さ(10)の合計17と平均値13.0との差の二乗

- a[6] = (13 - 13.0) ** 2 = 0.0 # 1個目のグッズの重さ(3),2個目のグッズの重さ(10)の合計13と平均値13.0との差の二乗

- a[7] = (20 - 13.0) ** 2 = 49.0 # 0個目のグッズの重さ(7),1個目のグッズの重さ(3),2個目のグッズの重さ(10)の合計20と平均値13.0との差の二乗

- a[8] = (10 - 13.0) ** 2 = 9.0 # 3個目のグッズの重さ(10)の合計10と平均値13.0との差の二乗

- a[9] = (17 - 13.0) ** 2 = 16.0 # 0個目のグッズの重さ(7),3個目のグッズの重さ(10)の合計17と平均値13.0との差の二乗

- a[10] = (13 - 13.0) ** 2 = 0.0 # 1個目のグッズの重さ(3),3個目のグッズの重さ(10)の合計13と平均値13.0との差の二乗

- a[11] = (20 - 13.0) ** 2 = 49.0 # 0個目のグッズの重さ(7),1個目のグッズの重さ(3),3個目のグッズの重さ(10)の合計20と平均値13.0との差の二乗

- a[12] = (20 - 13.0) ** 2 = 49.0 # 2個目のグッズの重さ(10),3個目のグッズの重さ(10)の合計20と平均値13.0との差の二乗

- a[13] = (27 - 13.0) ** 2 = 196.0 # 0個目のグッズの重さ(7),2個目のグッズの重さ(10),3個目のグッズの重さ(10)の合計27と平均 値13.0との差の二乗

- a[14] = (23 - 13.0) ** 2 = 100.0 # 1個目のグッズの重さ(3),2個目のグッズの重さ(10),3個目のグッズの重さ(10)の合計23と平均 値13.0との差の二乗

- a[15] = (30 - 13.0) ** 2 = 289.0 # 0個目のグッズの重さ(7),1個目のグッズの重さ(3),2個目のグッズの重さ(10),3個目のグッズの重さ(10)の合計30と平均値13.0との差の二乗

- a[16] = (9 - 13.0) ** 2 = 16.0 # 4個目のグッズの重さ(9)の合計9と平均値13.0との差の二乗

- a[17] = (16 - 13.0) ** 2 = 9.0 # 0個目のグッズの重さ(7),4個目のグッズの重さ(9)の合計16と平均値13.0との差の二乗

- a[18] = (12 - 13.0) ** 2 = 1.0 # 1個目のグッズの重さ(3),4個目のグッズの重さ(9)の合計12と平均値13.0との差の二乗

- a[19] = (19 - 13.0) ** 2 = 36.0 # 0個目のグッズの重さ(7),1個目のグッズの重さ(3),4個目のグッズの重さ(9)の合計19と平均値13.0との差の二乗

- a[20] = (19 - 13.0) ** 2 = 36.0 # 2個目のグッズの重さ(10),4個目のグッズの重さ(9)の合計19と平均値13.0との差の二乗

- a[21] = (26 - 13.0) ** 2 = 169.0 # 0個目のグッズの重さ(7),2個目のグッズの重さ(10),4個目のグッズの重さ(9)の合計26と平均値13.0との差の二乗

- a[22] = (22 - 13.0) ** 2 = 81.0 # 1個目のグッズの重さ(3),2個目のグッズの重さ(10),4個目のグッズの重さ(9)の合計22と平均値13.0との差の二乗

- a[23] = (29 - 13.0) ** 2 = 256.0 # 0個目のグッズの重さ(7),1個目のグッズの重さ(3),2個目のグッズの重さ(10),4個目のグッズの重さ(9)の合計29と平均値13.0との差の二乗

- a[24] = (19 - 13.0) ** 2 = 36.0 # 3個目のグッズの重さ(10),4個目のグッズの重さ(9)の合計19と平均値13.0との差の二乗

- a[25] = (26 - 13.0) ** 2 = 169.0 # 0個目のグッズの重さ(7),3個目のグッズの重さ(10),4個目のグッズの重さ(9)の合計26と平均値13.0との差の二乗

- a[26] = (22 - 13.0) ** 2 = 81.0 # 1個目のグッズの重さ(3),3個目のグッズの重さ(10),4個目のグッズの重さ(9)の合計22と平均値13.0との差の二乗

- a[27] = (29 - 13.0) ** 2 = 256.0 # 0個目のグッズの重さ(7),1個目のグッズの重さ(3),3個目のグッズの重さ(10),4個目のグッズの重さ(9)の合計29と平均値13.0との差の二乗

- a[28] = (29 - 13.0) ** 2 = 256.0 # 2個目のグッズの重さ(10),3個目のグッズの重さ(10),4個目のグッズの重さ(9)の合計29と平均 値13.0との差の二乗

- a[29] = (36 - 13.0) ** 2 = 529.0 # 0個目のグッズの重さ(7),2個目のグッズの重さ(10),3個目のグッズの重さ(10),4個目のグッズ の重さ(9)の合計36と平均値13.0との差の二乗

- a[30] = (32 - 13.0) ** 2 = 361.0 # 1個目のグッズの重さ(3),2個目のグッズの重さ(10),3個目のグッズの重さ(10),4個目のグッズ の重さ(9)の合計32と平均値13.0との差の二乗

- a[31] = (39 - 13.0) ** 2 = 676.0 # 0個目のグッズの重さ(7),1個目のグッズの重さ(3),2個目のグッズの重さ(10),3個目のグッズの重さ(10),4個目のグッズの重さ(9)の合計39と平均値13.0との差の二乗