問題
要約
-
AtCoder社には N 個のグッズが残っており、各グッズの重さは W_i 。
-
これらのグッズを D 袋の福袋に分けて販売する。
-
目標は、各福袋に入ったグッズの重さの合計の分散を最小にすること。
-
分散の定義：V = (1/D) * Σ(x_i - x̄)^2
ここで、x_i は各福袋の重さの合計、x̄ はそれらの平均。 -
条件：
- 空の福袋があってもよい（その場合、重さは0とする）
- 各グッズは必ずどれか1つの福袋に入れなければならない
-
求めるもの：最適な分け方をした時の分散の最小値
変数情報：
- N: グッズの総数
- W_i: i番目のグッズの重さ (1 ≤ i ≤ N)
- D: 福袋の数
既存投稿一覧ページへのリンク
独り言
何時間かけても解けなかった過去挑戦Ver
とりあえず、青色を目標にしている以上、E問題までは着実に解ける実力は付けておきたい。
特にDP問題ってパズル要素があるので、楽しいから難問でもあまり苦にならないし。
アプローチ
動的計画法を用いて、グッズの組み合わせと福袋の数に基づいて最適な分配を計算する。
ビット演算を活用して全ての組み合わせを探索し、各状態での最小の分散を計算する。
解法手順
-
入力を受け取り、グッズの総重量の平均値を計算する。
-
全てのグッズの組み合わせに対して、その重量の合計と平均値との差の二乗を事前計算する。
-
動的計画法のテーブルを初期化する。テーブルのサイズは(2^N) * (D+1)とし、各状態は「使用したグッズの組み合わせ」と「現在の福袋の数」で表す。
-
動的計画法を実行する：
a. 全てのグッズの組み合わせ（2^N通り）についてループを回す。
b. 各組み合わせに対して、そのサブセットを全て列挙する。
c. 各サブセットを新しい福袋に入れた場合の分散を計算し、最小値を更新する。 -
全てのグッズを使用し、D個の福袋を作った状態の分散を計算する。
-
最終的な分散の最小値を出力する。
ACコード
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との差の二乗