はまやんはまやんはまやん

hamayanhamayan's blog

Divide [第七回 アルゴリズム実技検定 M]

競技プログラミング

https://atcoder.jp/contests/past202107-open/tasks/past202107_m

前提知識

解説

https://atcoder.jp/contests/past202107-open/submissions/24472779

今回の問題は最小費用流が分かっていないと解けないので、どこかで学習してきてほしい。
最小費用流は分かっている前提で以降は進める。

どうやってひらめくか

フロー問題はこれはフローだと巧妙に隠してある場合が多いので、フローかなとまず発想を飛ばせるかが問題となる。
自分は大体不可能問題に当たったらフローだったみたいなパターンが多い気がする。
今回の問題でかなりややこしいのは、分解された部分列が連続しなくてもいいという部分であり、これはかなりややこしい。
DPも無理だし、貪欲も思いつかないし…フローかなとなる

フロー構築

頂点として以下の4種類を用意する

  • 始点st
  • 終点gl
  • 出頂点 x1, x2, ..., xN
  • 入頂点 y1, y2, ..., yN

ここから頂点を貼っていく。
まずはst -> glに流量N、コストCの辺を貼る。
これで流すと全部これに流れるので、すべての部分列に分解したと考えることになる。
この状態をベースに頂点と辺を増やしていこう。

すべてバラバラの状態から部分列として結合させていくようなイメージで考えていく。
例えば、A[2]とA[4]をくっつけて部分列とすることにすると、Cが1つ減ってabs(A[4]-A[2])が増えることになる。
これを流量を1つだけ別の所に流すような感じにする。
つまり、st -> x2 -> y4 -> glのように流れるように頂点を使って辺を貼ろう。
出頂点と入頂点を分けているのは、今回くっつけたときの次の要素というのはちょうど1つであり、
くっつけたときの前の要素というのもちょうど1つであるため、これをst -> x2で流量1、y4 -> glで流量1のようにして限定するためである。
ちょうどコストがかかりそうな所 x2 -> y4 について流量1、コストabs(A[4] - A[2])の辺とすればいい。
st -> x2, y4 -> glについてはコストは0にしておく。
これでくっつけた場合はCが減って、こっちの連結サイドに流れていくので、どっちが最適かなというのを最小費用流のアルゴリズムに選択してもらえばいい。

フロー構築まとめ

頂点

  • 始点st
  • 終点gl
  • 出頂点 x1, x2, ..., xN
  • 入頂点 y1, y2, ..., yN

辺 (流量,コスト)

  • st -> gl : (N,C)
  • st -> x? : (1,0)
  • x? -> y@ : (1,abs(A[@] - A[?])) ここで?＜@となるように注意する
  • y? -> gl : (1,0)

こういったグラフを作って、流量Nを流した時の最小費用が答えになる。

int N, C, A[202];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> C;
    rep(i, 0, N) cin >> A[i];

    atcoder::mcf_graph<int, ll> mcf(N * 2 + 2);
    int st = N * 2;
    int gl = N * 2 + 1;

    rep(i, 0, N) mcf.add_edge(st, i, 1, 0);
    rep(i, 0, N) rep(j, i + 1, N) mcf.add_edge(i, j + N, 1, abs(A[j] - A[i]));
    rep(i, 0, N) mcf.add_edge(i + N, gl, 1, 0);
    mcf.add_edge(st, gl, N, C);

    int flow;
    ll cost;
    tie(flow, cost) = mcf.flow(st, gl, N);

    cout << cost << endl;
}