AtCoder AGC 032 D - Rotation Sort (橙色, 1000 点)

本番フローで無理矢理解いた！！！
でも DP が本筋だね。

問題へのリンク

問題概要

の順列 が与えらえる。これを

• 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる
• 整数 を選んで区間 [ ) を右シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる

という操作を好きな順序で好きな回数だけ行ってソートしたい。ソートするのに必要な最小コストを求めよ。

制約

• 

考えたこと: まずは言い換え

一目見てメチャクチャ面白そうだと思った。
ちょっと考えてみると、操作は

• 要素を 1 個選んで、それを右に好きなだけ動かしていく。それにコストが かかる
• 要素を 1 個選んで、それを左に好きなだけ動かしていく。それにコストが かかる

という風に言い換えられることがわかった。左シフトとか右シフトとか考えるよりもずっとわかりやすくなる。

これを解く方法は何通りもありそう

editorial に近い DP

順列を隣接 swap したり、要素を 1 個選んで他に挿入したりする操作では、DP が有力なイメージはある。嬉しい性質は「選んだ要素を取り除いてあげたときに操作前後で要素の並びは変わらない」というのがある。これが DP できる所以となっているように思える。

これが「離れた二地点の swap」とかだと、またちょっと違う雰囲気を感じる。この辺りのことはフィーリングでしかなくて、まだイメージが変わるかもしれない。。。

似た問題として、以下のがある。これは単に LIS を求めるだけでよかった。

drken1215.hatenablog.com

LIS な DP をどう見るかによって、今回いろんな DP が作れそう。僕は

• LIS は動かす必要がないメンバーとしてとらえる (今回コストが左右で異なるので LIS が必要とは限らない)
• 動かす要素を左右どちらに動かすのかを同時に考えるとやりづらい
• 「右へ動かすと決めた要素は一旦除去してよい (除去するときにコストは加算する)」「除去しなかった範囲で単調増加になるように適宜大きいものを左に動かしたりする」

という風に考えた。そこで

• dp[i][j] := i 個まで見て、右にうごさないことを確定した最大の値が j である状態を実現する最小コスト (これより大きいやつは右へ動かすことが確定)

としてみた。これは BIT とか使って高速化する前の な LIS を求める以下の DP に割と対応している。

• dp[i][j] := i 個まで見て、最大が j である場合の LIS

実装は下の感じで通った。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void chmin(long long &a, long long b) { if (a > b) a = b; }

const long long INF = 1LL<<60;
int main() {
    long long N, A, B; cin >> N >> A >> B;
    vector<int> p(N);
    for (int i = 0; i < N; ++i) cin >> p[i];

    // dp[i][j] := i 個まで見て、右にうごさないことを確定した最大の値が j である状態を実現する最小コスト
    vector<vector<long long> > dp(N+1, vector<long long>(N+1, INF));
    dp[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= N; ++j) {
            if (dp[i][j] >= INF) continue;
            if (p[i] > j) {
                // p[i] は右にずらさない
                chmin(dp[i+1][p[i]], dp[i][j]);

                // p[i] を右にずらすことにする
                chmin(dp[i+1][j], dp[i][j] + A);
            }
            else {
                // p[i] を左にずらすしかない
                chmin(dp[i+1][j], dp[i][j] + B);
            }
        }
    }

    // 集計
    long long res = INF;
    for (int j = 0; j <= N; ++j) chmin(res, dp[N][j]);
    cout << res << endl;
}

本番でやった方法: フロー

という制約から、想定ではないんだろうなと思いつつフロー本番は通した。方針は

• なのに なペアをいかに解消するか --- か かどちらかを選んで動かせば良い
• を選ぶならコスト をかけて右に動かす
• を選ぶならコスト をかけて左に動かす

という構造になっている。それぞれの順序逆転ペアについて、左右のどちらを動かすかを選べて、その選択が他の順序逆転ペアにも影響が波及して行くイメージ。となるとフローっぽさが結構ある。

結局、

• 左ノード は各ノードにコスト を与え、ノード を選択した場合には値 を右に動かすことを表す
• 右ノード は各ノードにコスト を与え、ノード を選択した場合には値 を右に動かすことを表す

として

• なのに なペアに対して、左の と右の との間に辺を張る

としてあげて、「二部グラフの重み付き最小点被覆」を解いた。すなわちすべての逆順ペアをカバーして解消するのに必要な最小コストを求めた。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// edge class (for network-flow)
template<class FLOWTYPE> struct Edge {
    int rev, from, to;
    FLOWTYPE cap, icap;
    Edge(int r, int f, int t, FLOWTYPE c) : rev(r), from(f), to(t), cap(c), icap(c) {}
    friend ostream& operator << (ostream& s, const Edge& E) {
        if (E.cap > 0) return s << E.from << "->" << E.to << '(' << E.cap << ')';
        else return s;
    }
};

// graph class (for network-flow)
template<class FLOWTYPE> struct Graph {
    vector<vector<Edge<FLOWTYPE> > > list;
    
    Graph(int n = 0) : list(n) { }
    void init(int n = 0) { list.clear(); list.resize(n); }
    void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; }
    inline vector<Edge<FLOWTYPE> >& operator [] (int i) { return list[i]; }
    inline const size_t size() const { return list.size(); }
    
    inline Edge<FLOWTYPE> &redge(Edge<FLOWTYPE> e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    
    void addedge(int from, int to, FLOWTYPE cap) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0));
    }
    
    void add_undirected_edge(int from, int to, FLOWTYPE cap) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, cap));
    }
};

template<class FLOWTYPE> struct Dinic {
    const FLOWTYPE INF = 1LL<<60; // to be set
    vector<int> level, iter;

    Dinic() { }
    void dibfs(Graph<FLOWTYPE> &G, int s) {
        level.assign((int)G.size(), -1);
        level[s] = 0;
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (int i = 0; i < G[v].size(); ++i) {
                Edge<FLOWTYPE> &e = G[v][i];
                if (level[e.to] < 0 && e.cap > 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    
    FLOWTYPE didfs(Graph<FLOWTYPE> &G, int v, int t, FLOWTYPE f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < G[v].size(); ++i) {
            Edge<FLOWTYPE> &e = G[v][i], &re = G.redge(e);
            if (level[v] < level[e.to] && e.cap > 0) {
                FLOWTYPE d = didfs(G, e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    re.cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    FLOWTYPE solve(Graph<FLOWTYPE> &G, int s, int t) {
        level.assign((int)G.size(), -1); iter.assign((int)G.size(), 0);
        FLOWTYPE res = 0;
        while (true) {
            dibfs(G, s);
            if (level[t] < 0) return res;
            for (int i = 0; i < (int)iter.size(); ++i) iter[i] = 0;
            FLOWTYPE flow = 0;
            while ((flow = didfs(G, s, t, INF)) > 0) {
                res += flow;
            }
        }
    }
};




int N;
long long A, B;
vector<int> P;

int main() {
    cin >> N >> A >> B;
    P.resize(N);
    for (int i = 0; i < N; ++i) cin >> P[i], --P[i];

    Graph<long long> G(N*2 + 2);
    int s = N*2, t = s+1;
    for (int i = 0; i < N; ++i) {
        G.addedge(s, i, A);
        G.addedge(i+N, t, B);
    }
    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j < N; ++j) {
            int u = P[i], v = P[j];
            if (P[i] > P[j]) G.addedge(u, v+N, 1LL<<59);
        }
    }
    Dinic<long long> din;
    long long res = din.solve(G, s, t);
    cout << res << endl;
}