問題
雑記
サンプルはAC出来たし、アプローチの方法は間違っていないと思うんだけどなぁ・・・
解けないと分かっていれば、撤退できたけど、中途半端に「行けそう」感を持っていたせいで、普通に３時間溶かしてしまいました。
まだ力不足ですね。
アプローチ
ビットDPを用いて最適な分配を求め、最小の分散を計算する。
各状態をビット列で表現し、動的計画法を適用する。
解法手順
-
入力を受け取り、グッズの数N、福袋の数D、各グッズの重さWを取得する。
-
2^N個の全ての部分集合に対して、その集合に含まれるグッズの重さの合計を計算し、配列costに格納する。
-
DPテーブルを初期化する。最初は1つの福袋に全てのグッズを入れた場合の二乗和を格納する。
-
福袋の数を2からDまで増やしながら、以下の処理を繰り返す：
a. 新しいDPテーブルnew_DPを作成し、十分大きな値で初期化する。
b. 全ての状態Sに対して、その部分集合Tを列挙する。
c. DP[S^T] + cost[T]^2の最小値を求め、new_DP[S]に格納する。
d. 計算が終わったら、DPテーブルを更新する。 -
最終的なDP[-1]（全てのグッズを使用した状態）から分散を計算する。
分散 = (DP[-1] * D - sum(W)^2) / D^2 -
計算された分散を出力する。
WAコード
wa.py
import sys
# 1. 入力を受け取り、グッズの数N、福袋の数D、各グッズの重さWを取得する
N, D = map(int, input().split())
W = list(map(int, input().split()))
# 2. 2^N個の全ての部分集合に対して、その集合に含まれるグッズの重さの合計を計算し、配列costに格納する
# cost = [0] * (1 << N)
# for i in range(1, 1 << N):
# for j in range(N):
# if i & (1 << j):
# cost[i] += W[j]
# 高速化: ビット演算を使用してコストを計算
cost = [0] * (1 << N)
for S in range(1 << N):
cost[S] = sum(W[i] for i in range(N) if S >> i & 1)
# 3. DPテーブルを初期化する。最初は全ての状態を無限大で初期化し、空集合の状態を0にする
# DP = [float('inf')] * (1 << N)
# DP[0] = 0
# 高速化: DPテーブルをコストの二乗で初期化
DP = [c**2 for c in cost]
# 4. 福袋の数を1からDまで増やしながら、以下の処理を繰り返す
# for _ in range(1, D + 1):
for _ in range(2, D + 1): # 1つ目の福袋は既に計算済みなので2から開始
# a. 新しいDPテーブルnew_DPを作成し、十分大きな値で初期化する
# new_DP = [float('inf')] * (1 << N)
new_DP = [1 << 61] * (1 << N) # 十分大きな値として2^61を使用
# b. 全ての状態Sに対して処理を行う
for S in range(1 << N):
# c. その部分集合Tを列挙する
T = S
# while True:
while T: # Tが0になるまでループ
# DP[S^T] + cost[T]^2の最小値を求め、new_DP[S]に格納する
new_DP[S] = min(new_DP[S], DP[S ^ T] + cost[T] ** 2)
# if T == 0:
# break
T = (T - 1) & S
# d. 計算が終わったら、DPテーブルを更新する
DP = new_DP
# 5. 最終的なDP[-1]（全てのグッズを使用した状態）から分散を計算する
# total_weight = sum(W)
# mean = total_weight / D
# variance = (DP[-1] / D) - (mean ** 2)
# 高速化: 分散の計算を簡略化
variance = (DP[-1] * D - sum(W)**2) / D**2
# 6. 計算された分散を出力する
print(variance)