燃やす埋める練習問題１ - かんプリンの学習記録

燃やす埋める(Project Selection Problem)の練習問題についての解説です。

ポイント
問題概要
解説
提出プログラム
感想

ポイント

選択に対するコストからグラフを構築する

問題概要

${0,1}$ からなる文字列 ${S}$ が与えられます。 ${A_i}$ 円支払うことにより、 ${S_i}$ を( ${0}$ ならば ${1}$ に、 ${1}$ ならば ${0}$ に)変更することができます。また、 ${K}$ 個の区間 ${[L_k,R_k]}$ が与えられ、文字列 ${T=S_{L_k}S_{L_k+1}\dots S_{R_k}}$ について ${f(T)\times B_k}$ 円追加で支払う必要があります。

${f(T):=}$ 文字列 ${T}$ を回文にするために必要な文字の最小変更回数

例えば、 ${110101}$ を回文にするためには ${2,3}$ 文字目を変更する必要があるため ${f(110101)=2}$ となります。

適切に ${S}$ の文字を変更することにより、支払う金額を最小化してください。

${1 \leq N \leq 300}$
${1 \leq K \leq N(N-1)/2}$
${0\leq A_i,B_k \leq 10^9}$
${1\leq L_k < R_k\leq N}$
${S_i \in\{0,1\}}$

解説

燃やす埋める問題に関する基礎知識は以下の記事を参考にしてください．
kanpurin.hatenablog.com

各 ${S_i}$ を[変更しない/変更する]を選択肢とするのではなく、[0にする/1にする]を選択肢とします( ${f(T)}$ が最終的な ${S_i}$ の値に関する制約なので)。
もともと ${S_i=0}$ であるのものは以下のコストがかかります。

${S_i=1}$ であるのものも同様にして以下のコストがかかります。

${f(S_{L_k}S_{L_k+1}\dots S_{R_k})}$ の値は ${S_{L_k+i}\neq S_{R_k-i}}$ となるような ${i(0\leq i < \frac{R_k-L_k}{2})}$ の個数です。したがって、 ${S_{L_k+i}\neq S_{R_k-i}}$ となる場合に ${B_k}$ のコストがかかると考えます。

グラフを作成していきます。各文字に対応する頂点を作り、始点Sから各頂点に向けて有向辺を張り、各頂点から終点Tに向けて有向辺を張ります。このグラフの(S,T)カットで頂点 ${S_i}$ がS側の集合に含まれることを「 ${S_i}$ を ${0}$ にする」ことに、T側の集合に含まれることを「 ${S_i}$ を ${1}$ にする」ことに対応させます。上のコスト表を見ると、 ${S_i=0, S_j=1}$ か ${S_i=1, S_j=0}$ のときにコストをかけたいです。 ${S_i=0, S_j=1}$ にコスト ${B_k(\geq 0)}$ をかける場合、つまり頂点 ${S_i}$ がS側に、頂点 ${S_j}$ がT側にある際にコスト ${B_k}$ をかける場合は頂点 ${S_i}$ から頂点 ${S_j}$ に重み ${B_k}$ の有向辺を張ればよいです。

入力例1に対するグラフは以下のようになります。重み ${0}$ の辺は省略しています。

同じ頂点対 ${S_i,S_j}$ に辺を張る場合は ${B_k}$ をまとめて張ると辺の数は ${O(N^2)}$ となります。頂点数は ${O(N)}$ となるので、Dinicを用いると時間計算量 ${O(N^4)}$ 、Push-Relabelを用いると ${O(N^3)}$ で解くことができます。