競技プログラミングにハマるプログラマのスレ 258 (311ﾚｽ)
競技プログラミングにハマるプログラマのスレ 258 http://medaka.5ch.net/test/read.cgi/prog/1763044828/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
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
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 37 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.003s