かしのブログ

競技プログラミングとか

AtCoder Regular Contest 085 E - MUL

AtCoder 最大フロー最大フロー最小カット

問題

$N$ 個の宝石があり、 $i$ 個目の宝石の価値は $a_i$ （負の可能性もある）である。以下の操作を0回以上したとき、残っている宝石の価値の総和の最大値を求める。

正整数 $x$ を選び、 $x$ の倍数の宝石を全て割る

考察

各宝石を割らないグループ $\mathcal{S}$ と割るグループ $\mathcal{T}$ に分類する問題と捉える。

$a_i$ の大きさによって以下のような気持ちになる。

$a_i \geq 0$ のとき $\cdots$ 割らない方がいい
$a_i \lt 0$ のとき $\cdots$ 割ったほうがいい

また、操作は、「宝石 $n$ が割られているのなら、宝石 $kn$ も割らないといけない」という制約とみなす。これらより、次のようなペナルティを与える問題として、そのペナルティの最小化を目標とする。

$a_i \geq 0$ なる宝石 $i$ が $\mathcal{S}$ に属さないなら、ペナルティ $a_i$
$a_i \lt 0$ なる宝石 $i$ が $\mathcal{T}$ に属さないなら、ペナルティ $|a_i|$
$i \% j = 0$ なる宝石 $j$ が $\mathcal{T}$ に属し、宝石 $i$ が $\mathcal{T}$ に属さないならペナルティ $\infty$

グラフのカットの容量の最小化なので、双対問題である最大フロー問題として解くことができる。具体的には、宝石 $i$ に対応する頂点 $n_i$ と、頂点 $S, T$ を用意し、

$a_i \geq 0$ のとき、 $S\rightarrow ^{a_i} n_i$
$a_i \lt 0$ のとき、 $n_i \rightarrow ^{|a_i|} T$
$i \% j = 0$ のとき、 $n_i \rightarrow ^{\infty} n_j$

という辺を貼り、頂点 $S, T$ 間の最大フローを求める。これは発生する最小のペナルティなので、制約を無視して得られる最大得点からペナルティを引くと、価値の総和の最大値が得られる。

実装