AtCoder ABC 006 D - トランプ挿入ソート (試験管青色)

順列において、要素をどこかに挿入する系の操作をする問題は典型ではある。こういうのをしっかり押さえたい。

問題へのリンク

問題概要

の順列が与えられる。
以下の操作を繰り返してソートされた状態にしたい。最小回数を求めよ。

• 要素を 1 つ選んで、任意の場所に挿入する

制約

• 

考えたこと

順列を並び替える系の問題。
それも「遠く離れたものの swap」ではなく「挿入する」という操作。こういうのは DP で自然に扱えると相場は決まっている。

この問題の場合には結局 LIS (最長増加部分列) さえ求められたら、それに含まれないやつを適切に動かせば解くことができる。よって、LIS の長さを求めて、 から引けば良い。LIS は で求められる。

この問題の応用問題として、以下の AGC の問題がある。

atcoder.jp

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


// dp[i] := 長さが i の増加部分列として最後尾の要素のとりうる最小値
template<class T> int LIS(vector<T> a,  bool is_strong = true) {
    const T INF = 1<<30; // to be set appropriately
    int n = (int)a.size();
    vector<T> dp(n, INF);
    for (int i = 0; i < n; ++i) {
        if (is_strong) *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
        else *upper_bound(dp.begin(), dp.end(), a[i]) = a[i];
    }
    return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}


int main() {
    int N; cin >> N;
    vector<int> c(N);
    for (int i = 0; i < N; ++i) cin >> c[i];
    cout << N - LIS(c) << endl;
}