ARC107F
考えたこと
- 最小カット絡みであることは既知
- 頂点を削除して、連結成分に分ける
- 連結成分のBの和の絶対値がスコアになる
- うーん、連結成分をどう表現するのかさっぱりわからない
https://maspypy.com/atcoder-参加感想-2020-10-31arc107
- なるほど、わかった
- 一旦寝て明日見ないで考察しよう
- 絶対値は、正と負の最大値
- $\left|\sum x_i\right| = \max\left(\sum x_i, \sum -x_i\right)$
- これで絶対値が最大化問題に置き換わる
- 頂点を削除してスコアの最大化をするところと、スコアの計算自体の最大化とがあるので一旦分けて考える、つまりグラフは与えられて編集しないとする
- この時「プラスかマイナスかを選ぶ二択」なので二色塗り分けであり、カットになる
- 連結成分の中では同じものを選ばなければならない
- これは「もし二頂点u,vが隣接するなら、その二つの頂点の色は同じでなければならない」と変換できる
- 連結成分内で同一=隣接する頂点で同一
- これは互いにINFの辺を引くことで表現できる
- スコアは最大化したい。なので最大のスコアと比べた損失を辺の重みにして最小カットにする
- 素直に書くと負の辺がある(上の図)
- 十分大きな数N(ここでは10)をすべての辺に足したのが下図
- 最小カットは19で、2N-19が求める値になる
さて、ここまでで頂点が固定されてる時のスコアの計算はできた
次は頂点が削除される時だ
- 頂点を削除するしないの二択と正か負かの二択の二つがある
- 素朴にくっつけるとこうなる
- だけどこれではうまくいかない
- Sの右の辺がコスト0ならそこで切るのが最小になってしまう
- ここにも同様に10を乗せる？
- 3の頂点を消してるのに無限大辺の制約が生きてる(図で見落としてる)
- 「消さない」であって、かつ「負」の時にのみ「隣が負でなければ無限大ペナルティ」となるべき
まず「二つの二択の組み合わせ」についてもっと掘り下げる
- 今回「消す消さない」「正か負か」の2つの二択があるが、消す時には正か負か関係ない
- うーん、でもそれだと「消されてる時には負に塗られててもペナルティなし」みたいな表現が必要になるな…
公式解説
- なるほど、2つの頂点それぞれの塗りと2つの二択は対応しないで良いわけだ
- 最小カットで3以上の選択肢
- 2つの選択肢をそれぞれ頂点の塗りに対応させようとしない(論理積とかやりにくいので)
- かわりに掛け合わせの4通りに配置する
- TSはBAに無限大辺を引くことで消せる
- 残りの3つのうち、TTの時だけAはT、SSの時だけBはS
- 無限大辺は「根元がSのとき先がTではいけない」という制約。
- これで「ある頂点が正の時、隣は負ではいけない」を表現する(正負は交換してもここでは関係ない)
- なのでSSとTTを正と負に割り当てることに決まる(どちらがどちらでも良い)
- 最小カットなので3が正の時3得られることを-3とする、よくなる方向が小さい
- 辺が負になることをまずは気にしないで方向を合わせるのが混乱しないと思う
- 次に負の辺を無くすために適当にオフセットする
- [https://gyazo.com/1e35dad9482f692232a562bb5f
- 各辺を10増やした
- 最小カット
- これはつまり3を消して-4を4にする選択
- 10×2-16で4になる
