Codeforces Round #335 (Div. 1) A. Sorting Railway Cars

Codeforces Round #335(Div. 2) に参加しました。また D 問題の実装が詰め切れず 3 完…

ていうか今回 A 問題が一番難しくて B 問題が読解困難, C が一番手をつけやすかったという。

問題

codeforces.com

解法

例えば 9 3 4 5 6 7 8 2 1 という数列を考えると, 真ん中に「3 4 5 6 7 8」という 1 ずつ増加する数列があるので, ここは動かさないで 2, 1 をこの順に左に持っていく, 9 を右に持っていく, とやればソートされた数列を得ることが出来ます。

もうちょっと複雑にして, 3 4 2 5 6 9 7 8 1 という数列を考えると, やはり部分数列(?) に「3 4 5 6 7 8」が含まれるので, 上と同じようにすればソートされた数列を得ることが出来ます。

ということで, 注目すべきなのは「ある数から始まって, 1 ずつ連続した部分数列を考えた時の最長部分数列」です。Twitter でちょっと話題になってましたがこれは最長増加部分数列(LIS)とは少し違います。今回は 1 ずつ増加する, という制限があるからです。

で, じゃあこれをどうやって求めるかというと, dp っぽくやれば OK です。

dp[n] = (n から始まる上記の部分数列の最後の数の最大値) とすれば, n を大きい順に求めることで最長部分数列を求められます。

const int MAXN = 100010;
int p[MAXN], pos[MAXN], memo[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];
    for (int i = 0; i < n; i++) {
        pos[p[i]] = i;
    }
    for (int i = 0; i <= n; i++) memo[i] = i;
    for (int i = n; i >= 1; i--) {
        if (pos[i] < pos[i+1]) memo[i] = memo[i+1];
    }
    int ans = n;
    for (int i = 1; i <= n; i++) {
        ans = min(ans, n-(memo[i]-i+1));
    }
    cout << ans << endl;
    return 0;
}