Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 229 F 問題 Make Bipartite

AtCoder ABC ABC229 F問題 500 pts

問題

提出解答

問題の概要

外周が $N$ 頂点からなる車輪グラフ $W_N$ がある. ただし, ユニバーサル頂点は頂点 $0$ , 外周はある頂点から反時計回りに頂点 $1,2,\dots,N$ と名付けられている. 各辺に以下のように重みが設定されている.

辺 $0,i$ の重みは $A_i$ である.
辺 $i,(i+1)$ の重みは $B_i$ である (ただし, 頂点 $N+1$ は頂点 $1$ と見なす).

このグラフからいくつかの辺を除いて二部グラフにするとき, 除く辺の重みの総和の最小値を求めよ.

制約

$3 \leq N \leq 2 \times 10^5$
$1 \leq A_i, B_i \leq 10^9$
入力は全て整数

解法

$W_N$ の頂点を適切に部集合に分けた後, その分集合に従って二部グラフを構築するためには, 2つの端点が同じ部集合に属する辺を全て取り除かなくてはならず, 逆に, その辺を全て取り除けば十分である.

よって, 以下の問題に帰着できる.

$W_N$ の $N+1$ 個の頂点それぞれに青または赤を彩色する方法で, 端点に塗られている色が等しいような辺の重みの総和を最小にせよ.

ここで, 対称性から, 頂点 $0$ に塗る色は青であるとしてよい.

そして, 頂点 $1$ に塗る色が青である場合と, 赤である場合それぞれについての最小値を求め, 最後により小さい方を採用する.

まず, 頂点 $1$ が青である場合を考える. 動的計画法で解く. $i=1,2, \dots, N$ と $C \in \{B,R\}$ ( $B$ が青, $R$ が赤) に対して, ${\rm DP}[i,C]$ を

${\rm DP}[i,C]:=$ 頂点 $1,2,\dots, i$ から誘導される部分グラフにおける帰着問題の最小値. ただし, $i=N$ のときは辺 $N,1$ は無いものとする.

と定義する.

ベースケースとなる $i=1$ のときは, 今, 頂点 $1$ に塗る色を青と仮定していることから,

${\rm DP}[1,C]=\begin{cases} A_1 & (C=B) \\ \infty & (C=R) \end{cases}$

である.

次に, 遷移を考える. $i \geq 2$ に対して,

頂点 $i$ を青に塗る場合, ユニバーサル頂点との辺を除外せねばならず, 確実に $A_i$ の重みが発生し, 頂点 $i-1$ に塗る色を, $B_{i-1}$ の重みを受け入れて青にするか, 重みなしで赤にするかの2択になるので,

${\rm DP}[i][B]=\min({\rm DP}[i-1][B]+B_{i-1}, {\rm DP}[i-1][R])+A_i$

である.

頂点 $i$ を赤に塗る場合, ユニバーサル頂点との辺の除外は発生せず, 頂点 $i-1$ に塗る色を, 重みなしで青にするか, $B_{i-1}$ の重みを受け入れてで赤にするかの2択になるので,

${\rm DP}[i][R]=\min({\rm DP}[i-1][B], {\rm DP}[i-1][R]+B_{i-1})$

である.

そして, ${\rm DP}[N$ ] においては辺 $N,1$ を考慮していないので, 帳尻合わせをすると, 頂点 $1$ を青に塗る場合の最小値 $\alpha$ は

$\alpha:=\min({\rm DP}[N][B]+B_N, {\rm DP}[R])$

である.

頂点 $1$ に塗る色が赤の場合を考える. 大体は青の場合と同じだが, 以下の部分が変わる.

初期値は,

${\rm DP}'[1,C]=\begin{cases} \infty & (C=B) \\ 0 & (C=R) \end{cases}$

になる.

頂点 $1$ を赤に塗る場合の最小値 $\beta$ は $\beta=\min({\rm DP}[N][B], {\rm DP}[R]+B_N)$ である.

よって, 頂点 $1$ を青, 赤に塗るそれぞれの場合を考慮したので, 最終的な答えは $\min(\alpha, \beta)$ である. 計算量は $O(N)$ である.