ArraySorting [Single Round Match 779 Round 1 - Division I, Level One]

https://community.topcoder.com/stat?c=problem_statement&pm=15960

前提知識

• LIS

解説

なるべく少ない個数の要素を修正して、辞書順最小の非減少列を作成するという問題。

構築の部分は後で考えるとして、修正すべき要素数を考える。
修正すべき個数の最小化ではなく、修正しなくていい個数の最大化と言い換えてみよう。
すると、これはLISと同じ問題となる。
LISのよくある回答である、セグメントツリー解法などで解いてもよいが、今回はO(N²)が許されるので、
自分より前で最も長いLISを愚直に探そう。
この時に以下の配列を構築していく。

top[i] := 最後がA[i]であるLISの最大長
pre[i] := 最後がA[i]であるLISの1つ前の要素とでき、そのうち最も近いもの

LISとして固定するものが決まったら、その間をなるべく小さい数で埋めていくのだが、LISは何通りもある。
固定するLISはなるべく後ろにして、前に編集可能な部分を残してなるべく小さい数で埋めたい。
ここで配列preを使用する。
LISの長さが最長のものを固定するLISの末尾として、そこからpreを使ってさかのぼっていくと固定に最適なLISが得られる。
あとは、配列chkを使って、固定する要素に印をつけておいて、先頭から置ける最も小さい数で埋めていけばいい。

int top[2010], pre[2010], chk[2010];

struct ArraySorting {
    vector <int> arraySort(vector <int> A) {
        int n = A.size();
        rep(i, 0, n) {
            top[i] = 0;
            pre[i] = -1;

            rep(j, 0, i) if (A[j] <= A[i]) {
                if (top[i] <= top[j]) {
                    top[i] = top[j];
                    pre[i] = j;
                }
            }

            top[i]++;
        }

        int ma = 0;
        rep(i, 0, n) chmax(ma, top[i]);

        int ma_i = 0;
        rep(i, 0, n) if (ma == top[i]) ma_i = i;

        chk[ma_i] = 1;
        while (0 <= ma_i) {
            ma_i = pre[ma_i];
            if(0 <= ma_i) chk[ma_i] = 1;
        }

        int x = 1;
        rep(i, 0, n) {
            if (chk[i]) x = A[i];
            A[i] = x;
        }

        return A;
    }
};