競技プログラミングにハマるプログラマのスレ 258 (311ﾚｽ)
上下前次1-新
274(1): 11/15(土)23:08 AAS
何度も試行錯誤してたらやっとF解いてくれたわ
たぶん正しい解法だよな
平均 M = (?Ai)/N を計算し，割り切れなければ -1．
di = Ai−M（総和 0）とおき，di≠0 の添字だけを扱う．
「操作 1 回＝重み付き有向辺 1 本」と見ると，各連結成分は少なくとも（頂点数−1）本の辺を要し，スパン木で等号達成．
よって di≠0 の集合を「総和 0 の部分集合」に分割したときの成分数を最大化すれば，最小操作回数は m−（成分数）となる．
これは部分集合 DP：dp[mask]=max_{sum[s]=0, s⊆mask}(1+dp[mask\s]) を最下位ビット固定で計算．
復元は各成分で中心 r を取り，正 di を r に集め，次に r から負 di へ配ると |S|−1 回で実現できる。
上下前次1-新書関写板覧索設栞歴
あと 37 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.004s