競技プログラミングにハマるプログラマのスレ 258 (309ﾚｽ)
上下前次1-新

---

274(1): 11/15(土)23:08 AA×


[240|320|480|600|100%|JPG|べ|ﾚｽ栞|ﾚｽ消]
274: [sage] 2025/11/15(土) 23:08:55.70 何度も試行錯誤してたらやっと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 回で実現できる。 http://medaka.5ch.net/test/read.cgi/prog/1763044828/274
何度も試行錯誤してたらやっと解いてくれたわ たぶん正しい解法だよな 平均 を計算し割り切れなければ 総和 とおき の添字だけを扱う 操作 回重み付き有向辺 本と見ると各連結成分は少なくとも頂点数本の辺を要しスパン木で等号達成 よって の集合を総和 の部分集合に分割したときの成分数を最大化すれば最小操作回数は 成分数となる これは部分集合 を最下位ビット固定で計算 復元は各成分で中心 を取り正 を に集め次に から負 へ配ると 回で実現できる

---

上下前次1-新書関写板覧索設栞歴

---

あと 35 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.025s